On sets not belonging to algebras and rainbow matchings in graphs

Abstract

Motivated by a question of Grinblat, we study the minimal number $\mathfrak{v}(n)$ that satisfies the following. If $A_1,\dots ,A_n$ are equivalence relations on a set $X$ such that for every $i\in [n]$ there are at least $\mathfrak{v}(n)$ elements whose equivalence classes with respect to $A_i$ are nontrivial, then $A_1,\dots ,A_n$ contain a rainbow matching, i.e. there exist $2n$ distinct elements $x_1,y_1,\dots ,x_n,y_n\in X$ with $x_i{\sim }_{A_i}{y}_i$ for each $i\in [n]$. Grinblat asked whether $\mathfrak{v}(n)=3n-2$ for every $n\ge 4$. The best-known upper bound was $\mathfrak{v}(n)\le 16n/5+\mathcal{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 $\mathfrak{v}(n)=3n+o(n)$.