Rainbow Matchings and Algebras of Sets

Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence, 2002 ) asks the following question in the context of algebras of sets: What is the smallest number v = v ( n ) such that, if A 1 , … , A n are n equivalence relations on a common finite...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2017-03, Vol.33 (2), p.473-484
Main Authors: Nivasch, Gabriel, Omri, Eran
Format: Article
Language:English
Subjects:
Algebra
Combinatorial analysis
Combinatorics
Engineering Design
Equivalence
Grounds
Mathematical analysis
Mathematics
Mathematics and Statistics
Original Paper
Rainbows
Texts
Translations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Grinblat (Algebras of Sets and Combinatorics, Translations of Mathematical Monographs, vol. 214. AMS, Providence, 2002 ) asks the following question in the context of algebras of sets: What is the smallest number v = v ( n ) such that, if A 1 , … , A n are n equivalence relations on a common finite ground set X , such that for each i there are at least v elements of X that belong to A i -equivalence classes of size larger than 1, then X has a rainbow matching—a set of 2 n distinct elements a 1 , b 1 , … , a n , b n , such that a i is A i -equivalent to b i for each i ? Grinblat has shown that v ( n ) ≤ 10 n / 3 + O ( n ) . He asks whether v ( n ) = 3 n - 2 for all n ≥ 4 . In this paper we improve the upper bound (for all large enough n ) to v ( n ) ≤ 16 n / 5 + O ( 1 ) .
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-017-1764-9