1. On sets not belonging to algebras and rainbow matchings in graphs.
- Author
-
Clemens, Dennis, Ehrenmüller, Julia, and Pokrovskiy, Alexey
- Subjects
- *
GRAPH theory , *SET theory , *MATCHING theory , *PATHS & cycles in graph theory , *MULTIGRAPH - Abstract
Motivated by a question of Grinblat, we study the minimal number v ( n ) that satisfies the following. If A 1 , … , A n 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 A i are nontrivial, then A 1 , … , A n contain a rainbow matching, i.e. there exist 2 n distinct elements x 1 , y 1 , … , x n , y n ∈ X with x i ∼ A i y i for each i ∈ [ n ] . Grinblat asked whether v ( n ) = 3 n − 2 for every n ≥ 4 . The best-known upper bound was v ( n ) ≤ 16 n / 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 ) = 3 n + o ( n ) . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF