Improved bounds concerning the maximum degree of intersecting hypergraphs

MaRDI QIDQ6414541zbMATH OpenFDO

Authors Peter Frankl, Jian Wang

Publication date 20 October 2022

Abstract: For positive integers $n>k>t$ let $$ denote the collection of all $k$-subsets of the standard $n$-element set $[n]=1,ldots,n$. Subsets of $$ are called $k$-graphs. A $k$-graph $mathcalF$ is called $t$-intersecting if $|Fcap{F}^{\prime }|geqt$ for all $F,F^{\prime }inmathcalF$. One of the central results of extremal set theory is the ErdH{o}s-Ko-Rado Theorem which states that for $ngeq(k-t+1)(t+1)$ no $t$-intersecting $k$-graph has more than $$ 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 $mathcalF(i)=FsetminusicoloniinFinmathcalF$. The quantity $varrho(mathcalF)=maxlimit{s}_{1leqileqn}|mathcalF(i)|/|mathcalF|$ measures how close a $k$-graph is to a star. The main result (Theorem 1.5) shows that $varrho(mathcalF)>1/d$ holds if $mathcalF$ is 1-intersecting, $$ and $ngeq4(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 $tgeq2$ (Theorem 1.11) along with a number of related results.

This page was built for publication: Improved bounds concerning the maximum degree of intersecting hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6414541)