Michael Krivelevich: Large subgraphs without short cycles

Abstract: Given a fixed graph H and a large integer m, what is the minimum possible number of edges in a largest H-free subgraph of an m-edge graph G? While for a non-bipartite H the answer is fairly straightforward, the problem appears to be quite challenging for the bipartite case - just as is frequently the situation for bipartite Turan-type problems.

Here we consider this question for H being a cycle of length 2r, or more generally when the target subgraph should contain no even cycles of length up to 2r. We also treat a related problem of finding a subgraph of large minimum degree and without short even cycles in a graph with a given degree spread (minimum, maximum degrees).

Joint work with Florent Foucaud and Guillem Perarnau.