Linear growth conjecture for rainbow matching thresholds
Linear growth conjecture for rainbow matching thresholds
Let be the largest number of colors for which there exists an -colored -partite -graph without a rainbow -matching. Linear growth conjecture. For every there exists a constant such that
for all . This conjecture proposes the correct order of growth in 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
Sign in to submit a solution.
No solutions have been posted yet.