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

degreesforbidden subgraphsgirthprobabilistic methodsspanning subgraphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) 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)

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

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)