Options
On sets not belonging to algebras and rainbow matchings in graphs
Publikationstyp
Journal Article
Publikationsdatum
2016-06-17
Sprache
English
Institut
TORE-URI
Enthalten in
Volume
122
Start Page
109
End Page
120
Citation
Journal of Combinatorial Theory. Series B (122): 109-120 (2017)
Publisher DOI
Scopus ID
Publisher
Elsevier
Motivated by a question of Grinblat, we study the minimal number v(n) that satisfies the following. If A1,…,An are equivalence relations on a set X such that for every i∈[n] there are at least v(n) elements whose equivalence classes with respect to Ai are nontrivial, then A1,…,An contain a rainbow matching, i.e. there exist 2n distinct elements x1,y1,…,xn,yn∈X with xi∼Aiyi for each i∈[n]. Grinblat asked whether v(n)=3n−2 for every n≥4. The best-known upper bound was v(n)≤16n/5+O(1) due to Nivasch and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that v(n)=3n+o(n).
Schlagworte
edge colourings
equivalence classes
multigraphs
rainbow matchings
DDC Class
510: Mathematik