# Orientation of nonideal clutters

From Egres Open

Let [math]\mathcal{C}[/math] be a clutter on ground set *V*, and let [math]\mathcal{B}[/math] be its blocker. Is it true that [math]\mathcal{C}[/math] is nonideal if and only if there exist [math]p:{\mathcal C} \to V[/math] and [math]q: {\mathcal B} \to V[/math] such that

- [math]p(X)\in X[/math] for every [math]X \in {\mathcal C}[/math],
- [math]p(Y)\in Y[/math] for every [math]Y \in {\mathcal B}[/math],
- if [math]p(X)=q(Y)[/math], then [math]|X \cap Y|\gt1[/math]?

## Remarks

This was conjectured by T. Király. It can be shown by a polyhedral version of Sperner's Lemma ^{[1]} that no such functions exist for ideal clutters. It is also easy to see that it is enough to verify the conjecture for minimally non-ideal clutters. Pap^{[1]} showed that the conjecture is true if the core of [math]{\mathcal C}[/math] is cyclic (see Lehman's theorem).

## References

- ↑
^{1.0}^{1.1}J. Pap,*Integrality, complexity and colourings in polyhedral combinatorics*, Ph.D. thesis, pdf link