On sets not belonging to algebras and rainbow matchings in graphs

DOI10.1016/J.JCTB.2016.05.006zbMATH Open1350.05031arXiv1508.06437OpenAlexW2963808008MaRDI QIDQ345074FDOQ345074

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)

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)$.

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

Recommendations

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

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)

Cites Work

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

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)