Aharoni–Berger–Kotlar–Ziv degree-constrained matching conjecture

At least 8 years old · documented by

Let H\mathcal{H} be a simple 33-partite 33-graph with vertex classes AA, BB and CC. Suppose each vertex in AA has degree at least rr, and each vertex in B∪CB \cup C has degree at most rr. Aharoni–Berger–Kotlar–Ziv conjecture.

ν(H)≥r−1r∣A∣.\nu(\mathcal{H}) \geq \frac{r - 1}{r}\left|A\right|.

This degree-asymmetric statement extends the regular case and gives a lower bound in terms of the size of one vertex class. For r=nr=n, it is among the conjectures that generalize the open Ryser–Brualdi–Stein problem on Latin transversals, so its full generality remains difficult.

References

Primary source

Penny Haxell and Lothar Narins, “A Stability Theorem for Matchings in Tripartite 3-Graphs”, arXiv:1701.06451 (2017).

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.