Unavoidable subhypergraphs: a-clusters Applications of the delta system method

Zoltan Furedi
University of Illinois at Urbana-Champaign

One of the central problems of extremal hypergraph theory is the
description of unavoidable subhypergraphs, in other words,
the Turan problem.

Let $\mathbf{a}=(a_1,\dots,a_p)$ be a sequence of
positive integers, $k=a_1+\dots+a_p$.
An $\textbf{a}$-\emph{cluster} $\AA = \{ F_0, \dots, F_p\}$ is family of $k$-sets such that the sets $F_i\setminus F_0$ are pairwise disjoint ($1\leq i \leq p$), $|F_i\setminus F_0|=a_i$, and the sets $F_0\setminus F_i$ are pairwise disjoint as well.
$\AA$ has $2k$ vertices and it is unique up to isomorphisms.

With an intensive use of the delta-system method we prove that for $k > p$ and sufficiently large $n$, % $(n>~n_0(k))$, if $\FF$ is an $n$-vertex $k$-uniform family with $|\FF|$ exceeding the Erd\H os-Ko-Rado bound ${n-1 \choose k-1}$, then $\FF$ contains an $\mathbf a$-cluster.
The only extremal family consists of all the $k$-subsets containing a given element.

A joint work with Lale \"Ozkahya.


Back to Workshop III: Topics in Graphs and Hypergraphs