The Turan number of a family of graphs

04/25/2016 - 16:00
04/25/2016 - 17:00
Tao Jiang, Miami University
McGill University, 805 rue Sherbrooke O, salle/room Burnside 1205

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

Last edited by on Fri, 04/22/2016 - 13:55