Fair Matching Representation in K_{n,n} Partition

Conjecture 1.9 · arXiv:1611.03196

arXiv Conjecture low confidence— first stated 2016-11-10

Authors: Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, Ran Ziv

Status partial high confidence

Conjecture 1.9 from arXiv:1611.03196 remains open in full generality. The source paper established the conjecture for m=2 and m=3 via topological methods (Sperner's lemma). A 2024 follow-up by Othman and Berger (Discrete Mathematics) provides combinatorial reproofs for m=2 and m=3 and shows for m=4 that a perfect matching M always exists in K_{n,n} with total shortfall s(M)≤11, constituting partial progress on the m=4 case but not a full resolution. The conjecture for m≥4 remains open.

Cited literature (1)

partial Almost fair perfect matchings in complete bipartite graphs (2024)

Abeer Othman, Eli Berger · Discrete Mathematics · doi:10.1016/j.disc.2023.113865

Gives combinatorial reproofs of the conjecture for m=2 and m=3, and proves for m=4 that a perfect matching M in K_{n,n} always exists with s(M)≤11, providing partial progress on the m=4 case.

Reviewer notes. No arXiv preprint was found for the Othman–Berger (2024) paper; it appears to be published only as a journal article (Discrete Mathematics Vol. 347, No. 4, Article 113865). An unpublished 2014 result (Berger, Lo, Seymour) and a later reproof by Alon establish that a function f(m) exists bounding the shortfall by a value depending only on m, but this is weaker than the conjecture and these results remain unpublished. The conjecture is thus open for m≥4.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For any partition $E_1, E_2, \ldots, E_m$ of $E(K_{n,n})$ and any $j \leq m$ there exists a perfect matching $F$ in $K_{n,n}$ satisfying $|F \cap E_i| \geq \left\lfloor \frac{|E_i|}{n} \right\rfloor$ for all $i \neq j$, and $|F \cap E_j| \geq \left\lfloor \frac{|E_j|}{n} \right\rfloor - 1$.

Context

Central conjecture of the paper: the matching complex of $K_{n,n}$ admits almost fair representation of any partition of its edge set. The paper proves the conjecture for $m = 2$ and $m = 3$ (Theorem 1.10) using topological methods including Sperner's lemma.

Notes. PDF source — floor bracket symbols garbled as (cid:106)(cid:107); LaTeX reconstructed from context.

Source paper

Fair representation by independent sets
Ron Aharoni, Noga Alon, Eli Berger, Maria Chudnovsky, Dani Kotlar, Martin Loebl, Ran Ziv · 2016-11-10
https://arxiv.org/abs/1611.03196 PDF source