Graph removal lemmas
From MaRDI portal
Abstract: The graph removal lemma states that any graph on n vertices with o(n^{v(H)}) copies of a fixed graph H may be made H-free by removing o(n^2) edges. Despite its innocent appearance, this lemma and its extensions have several important consequences in number theory, discrete geometry, graph theory and computer science. In this survey we discuss these lemmas, focusing in particular on recent improvements to their quantitative aspects.
Recommendations
Cited in
(80)- Multigraphs (only) satisfy a weak triangle removal lemma
- The Bradley-Terry condition is \(L_1\)-testable
- H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
- Some intriguing upper bounds for separating hash families
- Bounds for graph regularity and removal lemmas
- The signless Laplacian spectral radius of graphs with no intersecting triangles
- A new bound for the Brown-Erdős-Sós problem
- The spectral radius of graphs with no intersecting odd cycles
- Induced arithmetic removal: complexity 1 patterns over finite fields
- A spectral condition for the existence of the square of a path
- On the local structure of oriented graphs -- a case study in flag algebras
- Efficient removal lemmas for matrices
- The maximum spectral radius of graphs without friendship subgraphs
- Sparse hypergraphs: new bounds and constructions
- Turán and Ramsey numbers in linear triple systems
- Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
- The removal lemma for tournaments
- The maximum spectral radius of wheel-free graphs
- Triangles in graphs without bipartite suspensions
- Removal and stability for Erdős-Ko-Rado
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Fast property testing and metrics for permutations
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- On linear configurations in subsets of compact abelian groups, and invariant measurable hypergraphs
- scientific article; zbMATH DE number 5354839 (Why is no real title available?)
- General deletion lemmas via the Harris inequality
- A sparse regular approximation lemma
- A counterexample to sparse removal
- On the KŁR conjecture in random graphs
- The joints problem for matroids
- Counting substructures. II: Hypergraphs
- A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
- Comparable pairs in families of sets
- Erdős-Pósa property for labeled minors: 2-connected minors
- Estimating parameters associated with monotone properties
- Efficient testing without efficient regularity
- Efficient removal lemmas for matrices
- On the testability of graph partition properties
- A generalized Turán problem and its applications
- A Ramsey variant of the Brown-Erdős-Sós conjecture
- Polynomial removal lemmas for ordered graphs
- Testing Linear-Invariant Properties
- Hypergraph removal lemmas via robust sharp threshold theorems
- Sparse hypergraphs with applications to coding theory
- The symmetry preserving removal Lemma
- Minimizing the number of 5-cycles in graphs with given edge-density
- The induced removal lemma in sparse graphs
- Correcting continuous hypergraphs
- New results on linear size distance preservers
- The regularity method for graphs with few 4‐cycles
- Removal lemmas and approximate homomorphisms
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Making an H H‐free graph k k‐colorable
- Minimum degree and the graph removal lemma
- Ramsey non-goodness involving books
- The minimum degree removal lemma thresholds
- A new proof of the graph removal lemma
- On regularity lemma and barriers in streaming and dynamic matching
- Regular decomposition of the edge set of a graph with applications
- A spectral Erdős-Rademacher theorem
- Probabilistic hypergraph containers
- On the generalized Turán problem for odd cycles
- Unavoidable patterns in locally balanced colourings
- Polynomial removal lemma for ordered matchings
- Abundance: asymmetric graph removal lemmas and integer solutions to linear equations
- Induced subgraph density. II: Sparse and dense sets in cographs
- The sparse regularity method with Schatten norms and entropy
- Perfect proper edge colorings of regular bipartite graphs with rainbow \(C_4\)-\(\mathrm{s}\)
- Positive co-degree densities and jumps
- Induced arithmetic removal for partition-regular patterns of complexity 1
- A spectral Erdős-Faudree-Rousseau theorem
- Fan-complete Ramsey numbers
- Spectral supersaturation: triangles and bowties
- Spectral extremal graphs for disjoint odd wheels
- An efficient asymmetric removal lemma and its limitations
- Asymmetric results about graph homomorphisms
- Arithmetic progressions, different regularity lemmas and removal lemmas
- A variant of the hypergraph removal lemma
- A correspondence principle between (hyper)graph theory and probability theory, and the (hyper)graph removal Lemma
- Generalizations of the removal lemma
This page was built for publication: Graph removal lemmas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875854)
