Non-idealness conjecture for sufficiently wise-intersecting clutters

A clutter is a family of sets none of which contains another. It is kk-wise intersecting if every subset of at most kk members has a common element, yet no element belongs to all members. It is ideal if its primal covering linear program has an integral optimum for every integral nonnegative cost vector.

Non-idealness conjecture. There exists an integer k4k\geq 4 such that every kk-wise intersecting clutter is non-ideal.

Intersecting clutters can nevertheless be ideal, so the conjecture predicts that sufficiently strong finite-wise intersection forces non-idealness. The source further conjectures that k=4k=4 suffices; the claim is presented as open.

Sources & referencesView supporting material

Primary source

Ahmad Abdi, Gérard Cornuéjols, Tony Huynh and Dabeen Lee, “Idealness of k-wise intersecting families”, arXiv:1912.00614 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.