On sets not belonging to algebras and rainbow matchings in graphs

DOI10.1016/J.JCTB.2016.05.006MaRDI QIDQ345074zbMATH OpenOpenAlexFDO

Authors Dennis Clemens, Julia Ehrenmüller, Alexey Pokrovskiy

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.06437

zbMATH Keywords

multigraphsequivalence classesrainbow matchingsedge colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Motivated by a question of Grinblat, we study the minimal number $mathfrakv(n)$ that satisfies the following. If $A_1,ldots,A_n$ are equivalence relations on a set $X$ such that for every $iin[n]$ there are at least $mathfrakv(n)$ elements whose equivalence classes with respect to $A_i$ are nontrivial, then $A_1,ldots,A_n$ contain a rainbow matching, i.e. there exist $2n$ distinct elements $x_1,y_1,ldots,x_n,y_{n}inX$ with $x_{i}si{m}_{A_i}{y}_i$ for each $iin[n]$. Grinblat asked whether $mathfrakv(n)=3n-2$ for every $ngeq4$. The best-known upper bound was $mathfrakv(n)leq16n/5+mathcalO(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 $mathfrakv(n)=3n+o(n)$.

Recommendations

• Large rainbow matchings in general graphs
• Rainbow matchings in bipartite multigraphs
• Cooperative conditions for the existence of rainbow matchings

Cites work

• scientific article; zbMATH DE number 1827099 (Why is no real title available?)
• An improved bound on the sizes of matchings guaranteeing a rainbow matching
• Combinatorial matrix theory
• Combinatorics: ancient and modern. With a foreword by Ronald Graham
• Families of sets not belonging to algebras and combinatorics of finite sets of ultrafilters
• Orthogonal Latin Rectangles
• Rainbow matchings and connectedness of coloured graphs
• Rainbow matchings in r-partite r-graphs
• Theorems on sets not belonging to algebras
• Transversals of latin squares and their generalizations

Cited in

(3)

• Degree conditions for matchability in 3-partite hypergraphs
• Representation of large matchings in bipartite graphs
• Rainbow independent sets in certain classes of graphs

This page was built for publication: On sets not belonging to algebras and rainbow matchings in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345074)