On sets not belonging to algebras and rainbow matchings in graphs

详细信息    查看全文

• 作者：Dennis Clemens^a ; ^{dennis.clemens@tuhh.de} ; Julia Ehrenmü ; ller^a ; ^{julia.ehrenmueller@tuhh.de} ; Alexey Pokrovskiy^b ; ^{alja123@gmail.com}
• 关键词：Rainbow matchings ; Edge colourings ; Multigraphs ; Equivalence classes
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：109-120
• 全文大小：356 K
• 卷排序：122

文摘

Motivated by a question of Grinblat, we study the minimal number v(n)v(n) that satisfies the following. If A1,…,AnA1,…,An are equivalence relations on a set X   such that for every i∈[n]i∈[n] there are at least v(n)v(n) elements whose equivalence classes with respect to AiAi are nontrivial, then A1,…,AnA1,…,An contain a rainbow matching, i.e. there exist 2n   distinct elements x1,y1,…,xn,yn∈Xx1,y1,…,xn,yn∈X with xi∼Aiyixi∼Aiyi for each i∈[n]i∈[n]. Grinblat asked whether v(n)=3n−2v(n)=3n−2 for every n≥4n≥4. The best-known upper bound was v(n)≤16n/5+O(1)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)v(n)=3n+o(n).