Strong maximality and minimality conjecture for bounded-edge hypergraphs
Let be a hypergraph whose edge sizes are bounded above by a natural number . A matching is a set of pairwise disjoint edges, a vertex cover is a set of vertices meeting every edge, and an edge cover is a set of edges whose union is . A matching, vertex cover, or edge cover is strongly maximal or strongly minimal according to the comparison of set differences in the source definition.
Strong maximality and minimality conjecture. Every such hypergraph has a strongly maximal matching, a strongly minimal vertex cover, and a strongly minimal edge cover.
Strongly minimal edge covers and strongly maximal matchings need not exist for arbitrary hypergraphs, so the bounded-edge-size hypothesis is essential. The conjecture is known for , while the general case remains open.
References
Primary source
Ron Aharoni, “Strongly maximal matchings and strongly minimal covers”, arXiv:2206.02576 (2022).
Additional references
3 papers in this index state this conjecture (2009–2022). The statement above is taken from the most recent of them; the others are arXiv:2102.04203, arXiv:0911.4010.
Progress summary
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.