Verlagslink DOI: 10.1016/j.jctb.2016.05.006
Titel: On sets not belonging to algebras and rainbow matchings in graphs
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Ehrenmüller, Julia 
Pokrovskiy, Alexey 
Schlagwörter: edge colourings; equivalence classes; multigraphs; rainbow matchings
Erscheinungs­datum: 17-Jun-2016
Verlag: Elsevier
Quellenangabe: Journal of Combinatorial Theory. Series B (122): 109-120 (2017)
Zusammenfassung (englisch): 
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
Zeitschrift: Journal of Combinatorial Theory. Series B 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

100
Letzte Woche
1
Letzten Monat
4
checked on 01.10.2022

SCOPUSTM   
Zitate

3
Letzte Woche
0
Letzten Monat
0
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.