Linear growth conjecture for rainbow matching thresholds

About 14 years old · traced to

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.

References

Primary source

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

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.