# 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).

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