The maximal-independent-set conjecture for graphs with perfect matchings

Let Γ\Gamma be a graph on nn vertices containing a perfect matching. A maximal independent set is an independent vertex set that is not properly contained in any larger independent set. The perfect-matching maximal-independent-set conjecture. Γ \Gamma contains at most

2n/22^{n/2}

maximal independent sets. This is posed as a conjecture about extremal enumeration in graphs with perfect matchings; the source gives no resolution, so the asserted bound remains open.

Sources & referencesView supporting material

Primary source

Nathanaël Hassler and Andrew Treglown, “Notes on sum-free sets in abelian groups”, arXiv:2506.17401 (2026).

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.