Campuses:

Turan Numbers of Expanded Forests

Tuesday, September 9, 2014 - 3:15pm - 4:05pm
Keller 3-180
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) 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).
MSC Code: 
37E25
Keywords: