Rainbow matchings in non-uniform hypergraph systems
Let $s\geq 1$, $r_1, r_2,\dots, r_{s+1}$ be given positive integers and $r=\max\{r_1, r_2,\ldots, r_{s+1}\}$. We prove that if $\mathcal{F} = \{\mathcal{F}_1, \ldots, \mathcal{F}_{s+1}\}$ is a family of hypergraphs on a ground set of $n$ vertices, $n\geq 4r^2(s+1)$, such that $\mathcal{F}_i\subseteq \binom{n}{r_i}$ and $|\mathcal{F}_i|>\binom{n}{r_i}-\binom{n-s}{r_i}-\binom{n-s-r}{r_i-1}+1$, for all $i \in [s+1]$, then $\mathcal{F}$ admits a rainbow matching of size $s+1$ or there exists $W \in \binom{[n]}{s}$ such that $W$ is a vertex cover of $\mathcal{F}_i$, for all $i \in [s+1]$. This improves upon the previously known range $n>2r^3s$ to $n>4r^2(s+1)$. Moreover, for a given family $\mathcal{F} = \{\mathcal{F}_1, \ldots, \mathcal{F}_{s+1}\}$ of hypergraphs $\mathcal{F}_i\subseteq \binom{n}{r_i}$, we give a best possible Ore-degree condition for $\mathcal{F}_{i}$'s that guarantees the existence of a rainbow matching of size $s+1$ for $\mathcal{F}$.
Authors
- Ghaffar Raeisi (ORCID: https://orcid.org/0000-0003-0313-8059)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16970
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint