Abstract
Unavoidable subhypergraphs: a-clusters Applications of the delta system method
Zoltan Furedi
Renyi Institute of Mathematics
One of the central problems of extremal hypergraph theory is the description of unavoidable subhypergraphs, in other words, the Turán problem.
Let \( \mathbf{a} = (a_1, \dots, a_p) \) be a sequence of positive integers, and let \( k = a_1 + \dots + a_p \).
An \( \mathbf{a} \)-cluster \( \mathcal{A} = \{ F_0, \dots, F_p \} \) is a family of \( k \)-sets such that the sets \( F_i \setminus F_0 \) are pairwise disjoint (\( 1 \le i \le p \)), \( |F_i \setminus F_0| = a_i \), and the sets \( F_0 \setminus F_i \) are pairwise disjoint as well. The family \( \mathcal{A} \) has \( 2k \) vertices and is unique up to isomorphism.
With intensive use of the delta-system method, we prove that for \( k > p \) and sufficiently large \( n \), if \( \mathcal{F} \) is an \( n \)-vertex \( k \)-uniform family with \( |\mathcal{F}| \) exceeding the Erd\H{o}s–Ko–Rado bound \( \binom{n-1}{k-1} \), then \( \mathcal{F} \) contains an \( \mathbf{a} \)-cluster. The only extremal family consists of all the \( k \)-subsets containing a given element.
Joint work with Lale \"Ozkahya.
Let \( \mathbf{a} = (a_1, \dots, a_p) \) be a sequence of positive integers, and let \( k = a_1 + \dots + a_p \).
An \( \mathbf{a} \)-cluster \( \mathcal{A} = \{ F_0, \dots, F_p \} \) is a family of \( k \)-sets such that the sets \( F_i \setminus F_0 \) are pairwise disjoint (\( 1 \le i \le p \)), \( |F_i \setminus F_0| = a_i \), and the sets \( F_0 \setminus F_i \) are pairwise disjoint as well. The family \( \mathcal{A} \) has \( 2k \) vertices and is unique up to isomorphism.
With intensive use of the delta-system method, we prove that for \( k > p \) and sufficiently large \( n \), if \( \mathcal{F} \) is an \( n \)-vertex \( k \)-uniform family with \( |\mathcal{F}| \) exceeding the Erd\H{o}s–Ko–Rado bound \( \binom{n-1}{k-1} \), then \( \mathcal{F} \) contains an \( \mathbf{a} \)-cluster. The only extremal family consists of all the \( k \)-subsets containing a given element.
Joint work with Lale \"Ozkahya.
No video available