Monday, April 25th, 2016 4pm-5pm Burnside 1205
Miami University
The Turan number of a family of graphs

Given a graph G, the Turan number ex(n,G) is defined to be the maximum number of edges in a graph on n vertices which does not contain G as a subgraph. The Turan number of a family of graphs is defined analogously. We are interested in the Turan number of the family of the graphs with average degree at least d and order at most t (denoted by F_{d,t}). We further assume d\geq 2. Note that determining the Turan number ex(n,F_{d,t}) may be viewed as a generalization of the well-known girth problem which asks for the maximum size of an n-vertex graph not containing a cycle of length less than g. Indeed, the girth problem may be viewed as the determination of ex(n, F_{2,t}). Random graphs give a lower bound on the Turan number of F_{d,t} of order Omega(n^{2-2/d). For integers d\geq 2, we give an almost matching upper bound of O(n^{2-2/d+c_{d,t}}) where c_{d,t} goes to 0 as t goes to infinity. This partially answers a question of Verstraete. As one ingredient of our proof, we establish a generalization of the well-known theorem on the Turan number of a cube. This is joint work with A. Newman. We will also mention some related Turan problems for bipartite graphs.

Winter 2016 Schedule