Large subgraphs without short cycles

DOI10.1137/140954416MaRDI QIDQ3453565zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Michael Krivelevich, Guillem Perarnau

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4928

zbMATH Keywords

girthforbidden subgraphsspanning subgraphsprobabilistic methodsdegrees

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Paths and cycles (05C38) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

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(delta,Delta,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$, $rgeq2$. In this case, we give bounds on $f(m,F)$ and $h(delta,Delta,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.

Recommendations

• An extremal problem for random graphs and the number of graphs with large even-girth
• On the structure of extremal graphs of high girth
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
• Maximum bipartite subgraphs in graphs without short cycles
• Subgraphs with large degrees and girth

Cited in

(14)

• Counting hypergraphs with large girth
• Random polynomial graphs for random Turán problems
• Inverse Turán numbers
• Large hypergraphs without tight cycles
• Expander spanning subgraphs with large girth
• Relative Turán numbers for hypergraph cycles
• Relative Turán problems for uniform hypergraphs
• New examples of graphs without small cycles and of large size
• LARGE -FREE SUBGRAPHS IN -CHROMATIC GRAPHS
• Short proofs of some extremal results. II.
• Triangle-free subgraphs of hypergraphs
• Inverting the Turán problem with chromatic number
• Maximum cardinality neighbourly sets in quadrilateral free graphs
• Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree

This page was built for publication: Large subgraphs without short cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453565)