Minimum degree and the graph removal lemma

DOI10.1002/JGT.22891zbMATH Open1522.05047arXiv2105.09194OpenAlexW3161702261WikidataQ124810225 ScholiaQ124810225MaRDI QIDQ6094041FDOQ6094041

Authors: Jacob Fox, Yuval Wigderson 

Publication date: 9 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: The clique removal lemma says that for every $rgeq3$ and $varepsilon>0$, there exists some $delta>0$ so that every $n$-vertex graph $G$ with fewer than $delta{n}^r$ copies of $K_r$ can be made $K_r$-free by removing at most $varepsilon{n}^2$ edges. The dependence of $delta$ on $varepsilon$ in this result is notoriously difficult to determine: it is known that $delt{a}^{-1}$ must be at least super-polynomial in $varepsilo{n}^{-1}$, and that it is at most of tower type in $logvarepsilo{n}^{-1}$. We prove that if one imposes an appropriate minimum degree condition on $G$, then one can actually take $delta$ to be a linear function of $varepsilon$ in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super-polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.

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

Recommendations

• Graph removal lemmas
• A new proof of the graph removal lemma
• Removal lemmas with polynomial bounds
• The induced removal lemma in sparse graphs
• A generalized Turán problem and its applications

zbMATH Keywords

chromatic thresholdhomomorphism thresholdgraph removal lemmaminimum degree conditions

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Cites Work

• Proof of the Seymour conjecture for large graphs
• On extremal problems of graphs and generalized graphs
• Title not available (Why is that?)
• On the structure of linear graphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• Some Theorems on Abstract Graphs
• On a problem of K. Zarankiewicz
• The core of a graph
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• On the chromatic number of triangle-free graphs of large minimum degree
• On a valence problem in extremal graph theory
• A new proof of the graph removal lemma
• Supersaturated graphs and hypergraphs
• Unavoidable patterns
• Graph removal lemmas
• Regularity partitions and the topology of graphons
• Testing subgraphs in large graphs
• Title not available (Why is that?)
• On the structure of triangle-free graphs of large minimum degree
• On the chromatic number of pentagon-free graphs of large minimum degree
• The Algorithmic Aspects of the Regularity Lemma
• The chromatic thresholds of graphs
• An approximate version of Sidorenko's conjecture
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Dense graphs with small clique number
• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• The homomorphism threshold of \({C_3, C_5}\)-free graphs
• Homomorphism thresholds for odd cycles
• On the structure of dense graphs with bounded clique number
• Regularity lemmas for stable graphs
• The removal lemma for tournaments
• On a problem of Erdős and Rothschild on edges in triangles
• On graphs decomposable into induced matchings of linear sizes

Cited In (5)

• Graph removal lemmas
• The minimum degree removal lemma thresholds
• A new proof of the graph removal lemma
• A generalized Turán problem and its applications
• Bounds for graph regularity and removal lemmas

This page was built for publication: Minimum degree and the graph removal lemma

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