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
Adam Mickiewicz University
Technical University of Denmark, DTU