Seymour's dyadic conjecture
Let be an ideal clutter with incidence matrix , meaning that the set-covering polyhedron is integral. For every integral weight vector , the dual set-covering linear program has an optimal solution whose coordinates are all dyadic rationals, i.e. each has the form for integers and nonnegative integers .
References
- The Local Dyadic Conjecture — arXiv — Mahtab Alghasi, Bertrand Guenin, Levent Tunel
Source: arXiv
Progress summary
A new special case gives dyadic optimal solutions for some covering systems, but the conjecture for all ideal clutters remains open.
Seymour’s conjecture asserts that every ideal clutter has a totally dual dyadic covering system. The global conjecture remains unresolved.
Known results
- The conjecture is known for odd-cycle clutters, -cuts and -joins of grafts, dicuts, and dijoins.
- If the minimum weighted covering value is , the dual problem has an optimal dyadic solution.
- For ideal clutters, the condition for every clutter member and blocker member implies total dual dyadicity; a more general power-of-two intersection condition also suffices.
- For binary clutters, the corresponding bound is .
2026 local special case
Mahtab Alghasi, Bertrand Guenin, and Levent Tunel report dyadic optimality when a binary clutter with minimal integer weights has an optimal face containing a -degenerate integral corner with . This is a substantive sufficient condition, not a proof of the global conjecture, and the reported result remains unverified here.
Current status (as of October 2026): A local sufficient condition has been reported, while Seymour’s conjecture for all ideal clutters remains open.
Sources
Solutions 0
No solutions have been posted yet.