Lehman's theorem
A clutter is minimally non-ideal if it is not ideal but every minor is ideal. A degenerate projective plane is a clutter on ground set [math]\{1,2,\dots,n\}[/math] with hyperedges [math]\{1,2\},\{1,3\},\dots,\{1,n\},\{2,3,\dots,n\}[/math].
Theorem (Lehman)[1] Let [math]{\mathcal C}[/math] be a minimally non-ideal clutter that is not a degenerate projective plane, and let [math]{\mathcal B}[/math] be its blocker. Then the clutter [math]{\mathcal C}'[/math] of minimum size members of [math]{\mathcal C}[/math] is an r-regular and r-uniform clutter for some r, and the clutter [math]{\mathcal B}'[/math] of minimum size members of [math]{\mathcal B}[/math] is s-regular and s-uniform for some s. Furthermore, each member of [math]{\mathcal C}'[/math] intersects one member of [math]{\mathcal B}'[/math] in [math]rs-n+1[/math] elements, and all other members of [math]{\mathcal B}'[/math] in 1 element.
Remarks
The clutter [math]{\mathcal C}'[/math] is called the core of [math]{\mathcal C}[/math].
References
- ↑ A. Lehman, The Width-Length Inequality and Degenerate Projective Planes, Cook, W. and P. D. Seymour (eds.), Polyhedral Combinatorics DIMACS vol.1 (1990), 101--105.
