|Publisher DOI:||10.1016/j.jctb.2016.05.006||Title:||On sets not belonging to algebras and rainbow matchings in graphs||Language:||English||Authors:||Clemens, Dennis
|Keywords:||edge colourings;equivalence classes;multigraphs;rainbow matchings||Issue Date:||17-Jun-2016||Publisher:||Elsevier||Source:||Journal of Combinatorial Theory. Series B (122): 109-120 (2017)||Journal or Series Name:||Journal of Combinatorial Theory. Series B||Abstract (english):||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).||URI:||http://hdl.handle.net/11420/4654||ISSN:||0095-8956||Institute:||Mathematik E-10||Type:||(wissenschaftlicher) Artikel|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on Sep 24, 2020
Add Files to Item
Note about this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.