Large subgraphs without short cycles

Graphs, Hypergraphs, and Computing

06 February 14:00 - 15:00

Michael Krivelevich - Tel Aviv University

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