Linear growth conjecture for rainbow matching thresholds

From papers

Let f(r,t)f(r,t) be the largest number of colors for which there exists an (f,t)(f,t)-colored rr-partite rr-graph without a rainbow tt-matching. Linear growth conjecture. For every rr there exists a constant crc_r such that

f(r,t)crtf(r,t)\leq c_r t

for all tt. This conjecture proposes the correct order of growth in tt after the Aharoni–Berger conjecture was refuted. The paper proves an exponential upper bound, but the claimed linear bound remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Roman Glebov, Benny Sudakov and Tibor Szabó, “How many colors guarantee a rainbow matching?”, arXiv:1211.0793 (2012).

Solutions 0

No solutions have been posted yet.