On degree bounds of $k$-uniform hypergraphs with bounded matching number

Abstract

We study the connection between the degree sequence of a $k$-uniform hypergraph and the size of its largest matching. Let $\mathcal{F}$ be a $k$-uniform hypergraph on $n$ vertices and let $d_1(\mathcal{F})\ge d_2(\mathcal{F})\ge \cdots \ge d_n(\mathcal{F})$ be the vertex degrees arranged in non-increasing order. For integers $k\ge 2$, $s\ge 2$ and $n>2sk$, we prove that if the $2sk$-th largest degree satisfies $d_{2sk}>\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)-\left(\genfrac{}{}{0ex}{}{n-s}{k-1}\right),$ then $\mathcal{F}$ contains a matching of size at least $s$. Moreover, by relaxing the range of $n$, we obtain the same bound for the $(k+2s-2)$-th largest degree vertex. Note that the number $k+2s-2$ is optimal. For a $k$-set of vertices $S\subseteq [n]$, the degree of $S$ is defined as $\hat{A}°(S)={\sum }_{v\in S}\hat{A}°(v)$, and the minimum of $\hat{A}°(S)$ over all non-edge $k$-subsets $S\notin E(\mathcal{F})$ of $V(\mathcal{F})$ is the \textit{Ore-degree} of $\mathcal{F}$, denoted by $\ddot{I}{ƒ}_k(\mathcal{F})$. Balogh, Palmer and Raeisi proved: for $s\ge 2$ and $n\ge 3k^2(s-1)$, if $\ddot{I}{ƒ}_k(\mathcal{F})>k\left(\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)-\left(\genfrac{}{}{0ex}{}{n-s}{k-1}\right)\right),$ then $\mathcal{F}$ contains a matching of size $s$. They also conjectured that the result holds when $n>sk$. As a corollary, we prove that the bound on $n$ can be taken to be linear in $sk$ ($n\ge 3sk$).

Topics & keywords