2017/01/23 by Ron Aharoni, RON AHARONI, David Howard +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · doi:10.1017/s0963548316000353
openalex publication_date 2017/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/19
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.