Skip to main content

Inverse Turán problems

The CEU Campus
Thursday, April 11, 2019, 12:15 pm

Venue: Rényi Institue, Big hall. 

For a given graph H, the classical Tur\'an number Undefined control sequence \ex is defined to be the

maximal number of edges which can be taken in an H-free subgraph of the complete

graph Kn. Briggs and Cox introduced a dual version of this problem whereby one

maximizes for a given number k, the number of edges in a ground graph G for

which Undefined control sequence \ex. We resolve a problem of Briggs and Cox in the negative by

showing that the inverse Tur\'an number of K2,t is Θ(n3/2), for all t2.

We also obtain improved bounds on the inverse Tur\'an number of even cycles and paths. 

Joint with Ervin Győri, Nathan Lemons, Casey Tompkins, Oscar Zamora