Importance: High ✭✭✭
 Author(s): Ding, Guoli
 Subject: Combinatorics » Optimization
 Keywords: clutter covering MFMC property packing
 Posted by: mdevos on: November 11th, 2007
Conjecture   Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

See Wikipedia's Clutter for definitions of clutter and clutter minors. The clutter is the degenerate projective plane with vertex set and edge set . If is a clutter, then for every positive integer we let denote the largest multiset of vertices of which hit every edge at least times. Note that and that .

We say that a clutter with , and has Lehman's property if , , , and the following properties are satisfied.

\item for every . \item for every . \item for \item if and . \item every lies in exactly edges of , edges of , and members of .

Although the conditions in Lehman's condition are extremely stringent, Lehman [L] showed that every minor minimal clutter with the MFMC property satisfies these properties. Since the MFMC property for implies (and the degenerate projective planes are minor minimal without MFMC), if true, the above conjecture would be a nice extension of Lehman's theorem.

Ding [D] proved this conjecture for , but it is open for all other cases.

## Bibliography

*[D] G. Ding, Clutters with tau_2=2 tau, Discrete Math. 115 (1993), no. 1-3, 141--152. MathSciNet.

[L] A. Lehman, On the width-length inequality, mimeographic notes, published 1979. Math. Program. 17, 403--417 MathSciNet.

* indicates original appearance(s) of problem.