Strong conjecture on transversals of large maximal independent sets

Less than 1 year old · traced to

Let 0<c<10<c<1 be a constant. For a graph GG, let MIS⁡(G)\operatorname{MIS}(G) denote its family of maximal independent sets, and define the family of large maximal independent sets by

MIS⁡large(G)={I∈MIS⁡(G):∣I∣≥cn}.\operatorname{MIS}_{\mathrm{large}}(G)=\{I\in\operatorname{MIS}(G): |I|\geq cn\}.

A transversal is a set of vertices meeting every member of this family. Strong conjecture. Every graph GG on nn vertices has a transversal of size o(n)o(n) for MIS⁡large(G)\operatorname{MIS}_{\mathrm{large}}(G). The source describes this as a stronger conjecture proposed tentatively, and provides no proof or counterexample; the supplied status evidence is inconsistent with the assertion and is therefore noted for review.

References

Primary source

Joshua Cooper and Isaiah Hollars, “Hitting all maximal independent sets in c-hollow graphs”, arXiv:2607.15486 (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.