2015/08/26 by Clemens, Dennis, Ehrenmüller, Julia, Pokrovskiy, Alexey
#03E05 #05C25 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.1508.06437
Motivated by a question of Grinblat, we study the minimal number \mathfrakv(n) that satisfies the following. If A1,…, An are equivalence relations on a set X such that for every i∈[n] there are at least \mathfrakv(n) elements whose equivalence classes with respect to Ai are nontrivial, then A1, …, An contain a rainbow matching, i.e. there exist 2n distinct elements x1,y1,…,xn,yn∈ X with xi∼Ai yi for each i∈ [n]. Grinblat asked whether \mathfrakv(n) = 3n-2 for every n≥ 4. The best-known upper bound was \mathfrakv(n) ≤ 16n/5 + O(1) due to Nivash and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that \mathfrakv(n) = 3n+o(n).