Full rainbow matchings in equivalence relations

Abstract

We show that if a multigraph $G$ with maximum edge-multiplicity of at most $\frac{\sqrt{n}}{{\log }^{2}n}$, is edge-coloured by $n$ colours such that each colour class is a disjoint union of cliques with at least $2n+o(n)$ vertices, then it has a full rainbow matching, that is, a matching where each colour appears exactly once. This asymptotically solves a question raised by Clemens, Ehrenmüller and Pokrovskiy, and is related to problems on algebras of sets studied by Grinblat in [Grinblat 2002].