Fair representation matching in bipartite graphs

Conjecture 1.15 · 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 open medium confidence

Conjecture 1.15 from arXiv:1611.03196 asks for an additive constant c(m) guaranteeing that any bipartite graph G with m edge-sets E_1,...,E_m admits a large matching (of size at least |E(G)|/Delta(G) - c(m)) in which no E_i is over-represented beyond the ceiling of |E_i|/Delta(G). No verified resolution of this conjecture was found in the literature after an exhaustive web search. The conjecture is from 2016 and appears to remain open as of May 2026.

Reviewer notes. No verified follow-up paper addressing Conjecture 1.15 was found after 5 web calls. A ScienceDirect paper titled 'Almost fair perfect matchings in complete bipartite graphs' appeared in search results but returned HTTP 403 and could not be verified; it is not included in since_posted. The internal reference arXiv:2212.11969 is a false positive from the corpus fuzzy-matching step. Confidence is medium rather than high because the conjecture is approximately 9 years old, making the absence of indexed follow-up somewhat less conclusive.

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

Conjecture. For every $m$ there exists a number $c(m)$ for which the following is true: if $G$ is a bipartite graph and $E_1, \ldots, E_m$ are any sets of edges, then there exists a matching $S$ in $G$ of size at least $\frac{|E(G)|}{\Delta(G)} - c(m)$ such that $|S \cap E_i| \leq \left\lceil \frac{|E_i|}{\Delta(G)} \right\rceil$ for all $i \leq m$.

Context

An under-representation formulation of the fair representation theme, motivated by the observation that over-representation fails when the sets do not form a partition. The authors suggest $c(m) = m/2$ may suffice. When the $E_i$ form a partition, condition (2) implies all but $c(m)$ sets are fairly represented.

Notes. PDF source — ceiling bracket symbols garbled as (cid:100)(cid:101); 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