Large subgraphs without short cycles

Abstract

We study two extremal problems about subgraphs excluding a family $\F$ of graphs. i) Among all graphs with $m$ edges, what is the smallest size $f(m,\F)$ of a largest $\F$--free subgraph? ii) Among all graphs with minimum degree $\delta$ and maximum degree $\Delta$, what is the smallest minimum degree $h(δ,Δ,\F)$ of a spanning $\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 $\F$ is composed of all even cycles of length at most $2r$, $r\ge 2$. In this case, we give bounds on $f(m,\F)$ and $h(δ,Δ,\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.

14 pages

References in corpus (1)

• Large subgraphs without complete bipartite graphs

Cited by in corpus (9)

• Large subgraphs without complete bipartite graphs
• Counting Hypergraphs with Large Girth
• Triangle-free Subgraphs of Hypergraphs
• Existence of spanning $\mathcal{F}$-free subgraphs with large minimum degree
• Relative Turán Problems for Uniform Hypergraphs
• Maximum $\mathcal{H}$-free subgraphs
• Bounds for approximating lower envelopes with polynomials of degree at most $d$
• Maximum Cardinality Neighbourly Sets in Quadrilateral Free Graphs
• Highly connected graphs have highly connected spanning bipartite subgraphs