← All problems

Seymour's dyadic conjecture

Let C\mathcal{C} be an ideal clutter with incidence matrix AA, meaning that the set-covering polyhedron {x∈R≥0E:Ax≥1}\{x\in\mathbb{R}_{\ge 0}^{E}:Ax\ge\mathbf{1}\} is integral. For every integral weight vector w∈Z≥0Ew\in\mathbb{Z}_{\ge 0}^{E}, the dual set-covering linear program max⁡{1Ty:ATy≤w, y≥0}\max\{\mathbf{1}^{\mathsf T}y:A^{\mathsf T}y\le w,\ y\ge 0\} has an optimal solution yy whose coordinates are all dyadic rationals, i.e. each yiy_i has the form ai/2kia_i/2^{k_i} for integers aia_i and nonnegative integers kik_i.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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, TT-cuts and TT-joins of grafts, dicuts, and dijoins.
  • If the minimum weighted covering value is 22, the dual problem has an optimal dyadic solution.
  • For ideal clutters, the condition ∣S∩B∣≤3\lvert S\cap B\rvert\leq 3 for every clutter member SS and blocker member BB implies total dual dyadicity; a more general power-of-two intersection condition also suffices.
  • For binary clutters, the corresponding bound is ∣S∩B∣≤5\lvert S\cap B\rvert\leq 5.

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 (k,ℓ)(k,\ell)-degenerate integral corner with k(ℓ+1)≤6k(\ell+1)\leq 6. 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.