The expansion method in Turan problems

Graphs, Hypergraphs, and Computing

20 March 14:00 - 15:00

Tao Jiang - Miami University

The expansion method is an effective tool for Turan problems for sparse graphs and hypergraphs. One of the early examples of its use is Bondy and Simonovits' proof that the Turan number ex(n,C_{2m}) of an even cycle C_{2m} is upper bounded by O(n^{1+1/m}). The method was subsequently refined by Faudree and Simonovits to obtain a similar upper bound on theta graphs.

We discuss some very recent results obtained using the expansion method (with sufficient modifications under various settings). The first of these results concerns the so-called linear Turan numbers of r-uniform linear cycles. We show that ex_L(n,C_{2m})=O(n^{1+1/m) and ex_L(n,C_{2m+1})=O(n^{1+1/m}). This answers a question of Kostochka, Mubayi, and Verstraete. The second concerns the Turan numbers of the family of graphs with average degree at least d and number of vertices at most t. We establish an upper bound O(n^{2-2/d+\epsilon(t)}, where for fixed d, \epsilon(t) tends to 0 as t goes to infinity. This almost matches the lower bound from the random graph. This partially answers a question of Verstraete and has some connection to an old conjecture of Simonovits.

The first result is joint with Collier-Cartaino and Graber. The second result is joint with Newman.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to