The Aharoni–Berger–Kotlar–Ziv fair representation conjecture

Let M1\mathcal{M}_1 and M2\mathcal{M}_2 be matroids on the same ground set EE, and assume that EE can be partitioned into kk independent sets in each matroid. For a set XEX\subseteq E, say that XX represents a set SES\subseteq E almost α\alpha-fairly if

SXαS1.|S\cap X|\ge \lfloor\alpha|S|\rfloor-1.

It represents a partition almost α\alpha-fairly if it does so for every part. Aharoni–Berger–Kotlar–Ziv conjecture. For every partition of EE, there exists a common independent set XX of M1\mathcal{M}_1 and M2\mathcal{M}_2 that represents the partition almost 1/k1/k-fairly. This conjecture seeks a uniformly fair common independent representative under simultaneous matroid independence constraints.

Sources & referencesView supporting material

Primary source

Hannaneh Akrami, Siyue Liu, Roshan Raj and László A. Végh, “Matroids are Equitable”, arXiv:2507.12100 (2025).

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.