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

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 BCB \cup C has degree at most rr. Aharoni–Berger–Kotlar–Ziv conjecture.

ν(H)r1rA.\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.

Sources & referencesView supporting material

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.