Rainbow matchings and algebras of sets

الأصل · EN

Grinblat (2002) asks the following question in the context of algebras of sets: What is the smallest number v = v(n) such that, if A₁,, Aₙ are n equivalence relations on a common finite ground set X, such that for each i there are at least v elements of X that belong to Aᵢ-equivalence classes of size larger than 1, then X has a rainbow matching---a set of 2n distinct elements a₁, b₁,, aₙ, bₙ, such that aᵢ is Aᵢ-equivalent to bᵢ for each i? Grinblat has shown that v(n) ≤ 10n/3 + O(√n). He asks whether v(n) = 3n-2 for all n≥ 4. In this paper we improve the upper bound (for all large enough n) to v(n) ≤ 16n/5 + O(1).