Minimum degree and the graph removal lemma

DOI10.1002/JGT.22891MaRDI QIDQ6094041zbMATH OpenOpenAlexWikidataFDO

Authors Jacob Fox, Yuval Wigderson

Publication date 9 October 2023

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

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

zbMATH Keywords

chromatic thresholdhomomorphism thresholdgraph removal lemmaminimum degree conditions

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

Cited in

(5)

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

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)