Turan Numbers of Expanded Forests
Presenter
September 9, 2014
Keywords:
- Graph, tree
MSC:
- 37E25
Abstract
The Turan number ex(n,H) of an r-graph H is the largest size of an n-vertex
r-graph that does not contain H. The famous Erdos-Sos conjectrure concerns the
Turan number of a tree T of k vertices. The difficulty lies in the fact that
there could be very different extremal families, disjoint cliques of sizes k-1
or in some cases a graph with (k-2)/2 vertices of degree n-1.
A hypergraph H is a hypergraph forest if its edges can be ordered as
{E_1,..., E_m} such that for all i>1 there exits an alpha(i) < i such that the
intersection of E_i with earlier members contained entirely in E_{alpha(i)}.
Many extremal set theoretic results, such as the Erdos-Ko-Rado theorem, can
be described in terms of Turan numbers of very specific r-forests, or partial
r-forests. In this work we are looking for the possible widest class of
hypergraph forests where the extremal family is kind of concentrated, it
consists of a few high degree vertices. For all rgeq 4, we show that if H is
a partial r-forest such that each edge has at least two degre 1 vertices then
ex(n,H)=(s(H)-1) {n choose r-1} + O(n^{r-2})
where s(H) is the minimum size of a 1-cross-cut of H. Using structural
stability we also obtain exact results implying many recent asymptotic bounds.
Most of the new results presented are joint with Tao Jiang (Miami University,
Ohio).