On a Generalization of the Ryser-Brualdi-Stein Conjecture

2013/05/27 by Ron Aharoni, Pierre Charbit, Aharoni, Ron +4 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics #Combinatorics (math.CO) #Computer science #Conjecture #Discrete Mathematics (cs.DM) #Discrete mathematics #Economics #Epistemology #FOS: Computer and information sciences #FOS: Mathematics #Generalization #Graph Labeling and Dimension Problems #Hypergraph #Limits and Structures in Graph Theory #Matching (statistics) #Mathematical analysis #Mathematics #Multitude #Order (exchange) #Philosophy #Physics #Rainbow #Statistics #cs.DM #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1305.6164

arxiv created 2013/05/27 · openalex publication_date 2013/05/27 · arxiv updated 2013/05/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

A rainbow matching for (not necessarily distinct) sets F₁,...,F_k of hypergraph edges is a matching consisting of k edges, one from each F_i. The aim of the paper is twofold - to put order in the multitude of conjectures that relate to this concept (some of them first presented here), and to present some partial results on one of these conjectures, that seems central among them.

Citations

• Ryser's Conjecture for Tripartite 3-Graphs
• On Representatives of Subsets

Cited by

• A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes

Related

• A note on improved bounds for hypergraph rainbow matching problems
• A Rainbow r-Partite Version of the Erdős–Ko–Rado Theorem
• Counterexamples on matchings in hypergraphs and full rainbow matchings in graphs
• Rainbow matchings in properly-colored hypergraphs
• On a conjecture of Stein