Seymour's quarter-integral packing conjecture for ideal clutters

Let C\mathcal{C} be a clutter over ground set VV. A packing is a nonnegative vector yR+Cy\in\mathbb{R}^{\mathcal{C}}_+ satisfying

CC:vCyC1for every vV.\sum_{C\in\mathcal{C}:v\in C}y_C\leq 1\qquad\text{for every }v\in V.

Its value is 1Ty\mathbf{1}^{\mathsf T}y, and τ(C)\tau(\mathcal{C}) denotes the covering number of C\mathcal{C}. The packing is 14\frac14-integral if every nonzero coordinate is at least 14\frac14 and is an integral multiple of 14\frac14.

Seymour's quarter-integral packing conjecture. Every ideal clutter C\mathcal{C} has a 14\frac14-integral packing of value τ(C)\tau(\mathcal{C}).

This conjecture is described as notoriously difficult and remains open even for binary clutters and for the clutter of postman sets of a graph. The paper derives consequences of it for wise-intersecting ideal clutters.

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.