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, ldots, 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, ldots, 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 $nge 4$. In this paper we improve the upper bound (for all large enough $n$) to $mathfrak v(n) le 16n/5 + O(1)$.
Download