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 
Ehrenmüller, Julia 
Pokrovskiy, Alexey 
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).
ISSN: 0095-8956
Institute: Mathematik E-10 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Sep 24, 2020

Google ScholarTM


Add Files to Item

Note about this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.