← All problems

Orientation of nonideal clutters

15 years old · documented by

Let VV be a finite set and let C\mathcal C be a clutter on VV, meaning a family of subsets of VV in which no member properly contains another. Its blocker B=b(C)\mathcal B=b(\mathcal C) is the clutter of inclusion-minimal transversals of C\mathcal C: sets meeting every member of C\mathcal C. The covering polyhedron is

P(C)={x∈R+V:x(X)≥1 for every X∈C},P(\mathcal C)=\{x\in\mathbb R_+^V:x(X)\ge 1\text{ for every }X\in\mathcal C\},

where x(X)=∑v∈Xxvx(X)=\sum_{v\in X}x_v. The clutter is ideal if this polyhedron is integral, and nonideal otherwise. The question is whether nonideality is equivalent to the existence of maps p:C→Vp:\mathcal C\to V and q:B→Vq:\mathcal B\to V such that

p(X)∈X(X∈C),q(Y)∈Y(Y∈B),p(X)\in X\quad(X\in\mathcal C),\qquad q(Y)\in Y\quad(Y\in\mathcal B),

and, for every X∈CX\in\mathcal C and Y∈BY\in\mathcal B,

p(X)=q(Y)⟹∣X∩Y∣>1.p(X)=q(Y)\quad\Longrightarrow\quad |X\cap Y|>1.

Pap (2012) Egres Open, Orientation of nonideal clutters

Background

The question translates integrality of a covering polyhedron into a compatibility condition between choices from a clutter and its blocker. A transversal meets each clutter edge, and blocker duality gives b(b(C))=Cb(b(\mathcal C))=\mathcal C; ideality is also preserved by taking the blocker. Thus the two selector maps are naturally paired. The proposed criterion is an application of polyhedral Sperner-type reasoning: for an ideal clutter, a suitable coloring of the facets of its covering polyhedron would force a vertex with all colors, which conflicts with the stipulated intersection condition. Pap (2012), §§1.4 and 3.3.8

The converse was conjectured by Tamás Király. Júlia Pap’s 2012 thesis presents it as a converse problem for the Sperner-based obstruction and establishes special cases. A central structural tool is Lehman’s theorem on minimally nonideal (mni) clutters: apart from the finite degenerate projective planes, an mni clutter and its blocker have cores whose minimum-size edges satisfy a highly regular incidence relation. Here a clutter is mni if it is nonideal but all its minors are ideal. Pap (2012), §§1.4 and 3.4.3 Egres Open, Orientation of nonideal clutters

References

Progress summary

Refreshed
Open

A reader-submitted claim says an 11-element counterexample disproves the conjecture, but no independent verification was found.

The conjecture, posed by Tamás Király and studied by Júlia Pap in 2012, asks whether every nonideal clutter admits compatible choices from it and its blocker. Its converse remains unsettled by the published results.

Known results

  • Ideal clutters admit no such selector maps, by a polyhedral Sperner argument (Pap, 2012).
  • It suffices to prove the converse for minimally nonideal clutters (Pap, 2012).
  • Lehman’s theorem gives the needed regular core incidence structure, yielding compatible choices on the cores.
  • The full converse is proved when the core is cyclic (Pap, 2012).

Community submission (unverified), November 7, 2026

A submitted manuscript argues that an 1111-element nonideal clutter has no selector maps on the clutter and its full blocker, which would refute the nonideal-implies-choice direction. The submission describes the work as AI-assisted, but the mathematical claim has not received independent assessment.

Current status (as of November 2026): The ideal-case obstruction and cyclic-core converse are established; an alleged 1111-element counterexample is unverified, so the general question remains open.

Solutions 1

A nonideal clutter without Kiraly choice mapsSee full solutionHide full solution

Result and scope. 11-element nonideal clutter has no p,q on clutter and full blocker satisfying membership and singleton-intersection exclusion; refutes intended nonideal-implies-choice direction

Complete proof: A nonideal clutter without Kiraly choice maps · PDF.

The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.

This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.