Large subgraphs without short cycles

We study two extremal problems about subgraphs excluding a family $\mathcal{F}$ of graphs: (i) Among all graphs with $m$ edges, what is the smallest size $f(m,\mathcal{F})$ of a largest $\mathcal{F}$-free subgraph? (ii) Among all graphs with minimum degree $\delta$ and maximum degree $\Delta$, what is the smallest minimum degree $h(\delta,\Delta,\mathcal{F})$ of a spanning $\mathcal{F}$-free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $\mathcal{F}$ is composed of all even cycles of length at most 2r, $r\geq 2$. In this case, we give bounds on $f(m,\mathcal{F})$ and $h(\delta,\Delta,\mathcal{F})$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$, we show the existence of subgraphs with arbitrarily high girth and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.



Read More: http://epubs.siam.org/doi/10.1137/140954416