Improved bounds concerning the maximum degree of intersecting hypergraphs

Abstract

For positive integers $n>k>t$ let $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ denote the collection of all $k$-subsets of the standard $n$-element set $[n]=\{1,\dots ,n\}$. Subsets of $\left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ are called $k$-graphs. A $k$-graph $\mathcal{F}$ is called $t$-intersecting if $|F\cap F^{\prime }|\ge t$ for all $F,F^{\prime }\in \mathcal{F}$. One of the central results of extremal set theory is the Erdős-Ko-Rado Theorem which states that for $n\ge (k-t+1)(t+1)$ no $t$-intersecting $k$-graph has more than $\left(\genfrac{}{}{0ex}{}{n-t}{k-t}\right)$ edges. For $n$ greater than this threshold the $t$-star (all $k$-sets containing a fixed $t$-set) is the only family attaining this bound. Define $\mathcal{F}(i)=\{F\setminus \{i\}:i\in F\in \mathcal{F}\}$. The quantity $\varrho (\mathcal{F})=\underset{1\le i\le n}{\max }|\mathcal{F}(i)|/|\mathcal{F}|$ measures how close a $k$-graph is to a star. The main result (Theorem 1.5) shows that $\varrho (\mathcal{F})>1/d$ holds if $\mathcal{F}$ is 1-intersecting, $|\mathcal{F}|>2^d{d}^{2d+1}\left(\genfrac{}{}{0ex}{}{n-d-1}{k-d-1}\right)$ and $n\ge 4(d-1)dk$. Such a statement can be deduced from the results of \cite{F78-2} and \cite{DF}, however only for much larger values of $n/k$ and/or $n$. The proof is purely combinatorial, it is based on a new method: shifting ad extremis. The same method is applied to obtain some nearly optimal bounds in the case of $t\ge 2$ (Theorem 1.11) along with a number of related results.

35 pages