Rainbow matchings and algebras of sets

Abstract

Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number $\mathfrak{v}=\mathfrak{v}(n)$ such that, if $A_1,\dots ,A_n$ are $n$ equivalence relations on a common finite ground set $X$, such that for each $i$ there are at least $\mathfrak{v}$ elements of $X$ that belong to $A_i$-equivalence classes of size larger than $1$, then $X$ has a rainbow matching---a set of $2n$ distinct elements $a_1,b_1,\dots ,a_n,b_n$, such that $a_i$ is $A_i$-equivalent to $b_i$ for each $i$? Grinblat has shown that $\mathfrak{v}(n)\le 10n/3+O(\sqrt{n})$. He asks whether $\mathfrak{v}(n)=3n-2$ for all $n\ge 4$. In this paper we improve the upper bound (for all large enough $n$) to $\mathfrak{v}(n)\le 16n/5+O(1)$.

Revision taking into account referees' comments. 12 pages, 7 figures