Orientation of nonideal clutters

From Egres Open
Jump to: navigation, search

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]?


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).


  1. 1.0 1.1 J. Pap, Integrality, complexity and colourings in polyhedral combinatorics, Ph.D. thesis, pdf link