Orientation of nonideal clutters

Definitions and mathematical statement

Let $\mathcal C$ be a nonempty family of nonempty subsets of a finite set $V$, with no member properly containing another; such a family is a clutter. Its blocker $\mathcal B$ is the family of inclusion-minimal sets $Y\subseteq V$ meeting every $X\in\mathcal C$. For $x\in\mathbb R^V$ write $x(X)=\sum_{v\in X}x_v$ and define \[ Q(\mathcal C)=\{x\in\mathbb R_{\ge0}^V: x(X)\ge1\ (X\in\mathcal C)\}. \] The clutter is ideal if every vertex of this polyhedron is integral, and nonideal otherwise. Here a vertex is an extreme point, not a ground-set element.

Is nonideality equivalent to the existence of representative choices \[ p:\mathcal C\to V,\quad q:\mathcal B\to V, \qquad p(X)\in X,\quad q(Y)\in Y, \] such that, for every $X\in\mathcal C$ and $Y\in\mathcal B$, \[ p(X)=q(Y)\ \Longrightarrow\ |X\cap Y|>1? \] Thus a primal edge and a minimal transversal meeting in exactly one element must not both select that element.

Each choice is made once for its entire set, consistently across all comparisons. The blocker contains all minimal transversals, not an arbitrarily selected subfamily. The implication excluding such choices for ideal clutters is known in the source; the conjectural direction is that every nonideal clutter admits them. This is a characterization of nonintegrality, without an asserted efficient method for listing the blocker, which may be exponentially large.

Short English statement

Is a clutter nonideal exactly when it and its blocker admit representative choices avoiding agreement at singleton intersections?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000060 (AMR-029-0060), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Orientation of nonideal clutters. Original source indexed by AMR-029-0060. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Orientation of nonideal clutters. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Orientation_of_nonideal_clutters.