Fair representation matching in bipartite graphs

AX_fair_representation_bipartite_matching_under_representation

Source: arXiv:1611.03196 — Fair representation by independent sets

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 ai-proved high confidence

The conjecture holds with the explicit crude bound c(m)=32(m+1)^3, by combining Carathéodory reduction with proportional-necklace interpolation between two matchings.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

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