The bounded-error conjecture for equitable matroid partitions

About 1 year old · traced to

Let M=(E,I)\mathcal{M}=(E,\mathcal{I}) be a matroid whose ground set EE can be partitioned into kk disjoint bases, and let S1,S2,…,SℓS_1,S_2,\ldots,S_\ell be pairwise disjoint subsets of EE. Bounded-error equitable partition conjecture. There exists a function f : N→Nf\,:\,\mathbb{N}\to\mathbb{N} such that there is a partition of EE into kk disjoint bases B1,…,BkB_1,\ldots,B_k satisfying

∣∣Bi∩Sj∣−∣Sj∣/k∣≤f(ℓ)\left||B_i\cap S_j|-|S_j|/k\right|\le f(\ell)

for all i∈[k]i\in [k] and j∈[ℓ]j\in[\ell]. This conjecture asks whether the discrepancy can be bounded solely in terms of the number of distinguished subsets, independently of the matroid, kk, and their sizes.

References

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.