A Rainbow r-Partite Version of the Erdős–Ko–Rado Theorem. (23rd January 2017)

• Record Type: Journal Article
• Authors: AHARONI, RON; HOWARD, DAVID
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 3(2017:May)
• Page Start: 321
• Page End: 337
• Publication Date: 2017-01-23
• Subjects: Primary 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548316000353
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Let [ n ] r be the complete r -partite hypergraph with vertex classes of size n . It is an easy exercise to show that every set of more than ( k −1) n r −1 edges in [ n ] r contains a matching of size k . We conjecture the following rainbow version of this observation: if F 1, F 2, . . ., F k ⊆ [ n ] r are of size larger than ( k −1) n r −1 then there exists a rainbow matching, that is, a choice of disjoint edges f i ∈ F i . We prove this conjecture for r =2 and r =3.