UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

On sets not belonging to algebras and rainbow matchings in graphs

Clemens, D; Ehrenmüller, J; Pokrovskiy, A; (2017) On sets not belonging to algebras and rainbow matchings in graphs. Journal of Combinatorial Theory, Series B , 122 pp. 109-120. 10.1016/j.jctb.2016.05.006. Green open access

[thumbnail of 1508.06437.pdf]
Preview
Text
1508.06437.pdf - Accepted Version

Download (377kB) | Preview

Abstract

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).

Type: Article
Title: On sets not belonging to algebras and rainbow matchings in graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1016/j.jctb.2016.05.006
Publisher version: https://doi.org/10.1016/j.jctb.2016.05.006
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Rainbow matchings, Edge colourings, Multigraphs, Equivalence classes
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10105840
Downloads since deposit
29Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item