Videos

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