Extremal results in sparse pseudorandom graphs
From MaRDI portal
Abstract: Szemer'edi's regularity lemma is a fundamental tool in extremal combinatorics. However, the original version is only helpful in studying dense graphs. In the 1990s, Kohayakawa and R"odl proved an analogue of Szemer'edi's regularity lemma for sparse graphs as part of a general program toward extending extremal results to sparse graphs. Many of the key applications of Szemer'edi's regularity lemma use an associated counting lemma. In order to prove extensions of these results which also apply to sparse graphs, it remained a well-known open problem to prove a counting lemma in sparse graphs. The main advance of this paper lies in a new counting lemma, proved following the functional approach of Gowers, which complements the sparse regularity lemma of Kohayakawa and R"odl, allowing us to count small graphs in regular subgraphs of a sufficiently pseudorandom graph. We use this to prove sparse extensions of several well-known combinatorial theorems, including the removal lemmas for graphs and groups, the ErdH{o}s-Stone-Simonovits theorem and Ramsey's theorem. These results extend and improve upon a substantial body of previous work.
Recommendations
Cites work
- scientific article; zbMATH DE number 5853068 (Why is no real title available?)
- scientific article; zbMATH DE number 3885945 (Why is no real title available?)
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 4099367 (Why is no real title available?)
- scientific article; zbMATH DE number 3470438 (Why is no real title available?)
- scientific article; zbMATH DE number 3487493 (Why is no real title available?)
- scientific article; zbMATH DE number 3609704 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1944144 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3298603 (Why is no real title available?)
- scientific article; zbMATH DE number 3188526 (Why is no real title available?)
- A Disproof of a Conjecture of Erdős in Ramsey Theory
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- A Spectral Turán Theorem
- A Szemerédi-type regularity lemma in abelian groups, with applications
- A combinatorial proof of the removal lemma for groups
- A correlation inequality for bipartite graphs
- A generalization of Turán's theorem
- A new proof of the graph removal lemma
- A new upper bound for diagonal Ramsey numbers
- A probabilistic counting lemma for complete graphs
- A variant of the hypergraph removal lemma
- Additive approximation for edge-deletion problems
- An approximate version of Sidorenko's conjecture
- An efficient sparse regularity concept
- Approximating the Cut-Norm via Grothendieck's Inequality
- Approximating the independence number via the -function
- Bounds for graph regularity and removal lemmas
- Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
- Combinatorial theorems in sparse random sets
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Cutting a graph into two dissimilar halves
- Efficient testing of large graphs
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Explicit Construction of Small Folkman Graphs
- Explicit Ramsey graphs and orthonormal labelings
- Extremal results for odd cycles in sparse pseudorandom graphs
- Extremal results for random discrete structures
- Hypergraph containers
- Hypergraph regularity and the multidimensional Szemerédi theorem
- Imbalances in k‐colorations
- Independent sets in hypergraphs
- Induced Ramsey-type theorems
- Induced-universal graphs for graphs with bounded maximum degree
- Lifts, discrepancy and nearly optimal spectral gap
- Limits of dense graph sequences
- Lower bounds of tower type for Szemerédi's uniformity lemma
- On Sets of Acquaintances and Strangers at any Party
- On \(K^ 4\)-free subgraphs of random graphs
- On graphs with linear Ramsey numbers
- On induced Ramsey numbers for graphs with bounded maximum degree
- On sets of integers containing k elements in arithmetic progression
- On the Folkman Numberf(2, 3, 4)
- On the KŁR conjecture in random graphs
- On the Minimal Density of Triangles in Graphs
- On the Ramsey multiplicities of graphs—problems and recent results
- On the structure of linear graphs
- Pseudo-random graphs
- Quasi-Random Set Systems
- Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
- Quasi-random graphs
- Quasirandom Groups
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- Quasi‐random graphs with given degree sequences
- Ramsey properties of random discrete structures
- Regular pairs in sparse random graphs I
- Regularity Lemma for k-uniform hypergraphs
- Regularity lemmas for graphs
- Small subsets inherit sparse \(\varepsilon\)-regularity
- Sparse partition universal graphs for graphs of bounded degree
- Sparse quasi-random graphs
- Szemerédi's regularity Lemma for matrices and sparse graphs
- Szemerédi’s Regularity Lemma for Sparse Graphs
- The Algorithmic Aspects of the Regularity Lemma
- The Ramsey number of a graph with bounded maximum degree
- The clique density theorem
- The counting lemma for regular k‐uniform hypergraphs
- The number of cliques in graphs of given order and size
- The primes contain arbitrarily long arithmetic progressions
- The sparse regularity lemma and its applications
- There exist graphs with super‐exponential Ramsey multiplicity constant
- Threshold Functions for Ramsey Properties
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Turán's extremal problem in random graphs: Forbidding even cycles
- Turán's theorem for pseudo-random graphs
- Two remarks on the Burr-Erdős conjecture
Cited in
(35)- A sequence of triangle-free pseudorandom graphs
- The regularity method for graphs with few 4‐cycles
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- On replica symmetry of large deviations in random graphs
- Polynomial configurations in subsets of random and pseudo-random sets
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- \(L_p\) regular sparse hypergraphs: box norms
- An undecidability result on limits of sparse graphs
- Turán numbers of bipartite graphs plus an odd cycle
- A weighted regularity lemma with applications
- A counterexample to the Bollobás–Riordan conjectures on sparse graph limits
- On two-point configurations in subsets of pseudo-random sets
- A new proof of the KŁR conjecture
- Arithmetic progressions, different regularity lemmas and removal lemmas
- Counting in hypergraphs via regularity inheritance
- A counting lemma for sparse pseudorandom hypergraphs
- Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs
- A relative Szemerédi theorem
- A sparse regular approximation lemma
- Discrepancy and eigenvalues of Cayley graphs
- Powers of Hamilton cycles in pseudorandom graphs
- Finding any given 2‐factor in sparse pseudorandom graphs efficiently
- Regularity inheritance in pseudorandom graphs
- A unified view of graph regularity via matrix decompositions
- On the KŁR conjecture in random graphs
- Forcing quasirandomness with triangles
- An analytic approach to sparse hypergraphs: hypergraph removal
- A probabilistic counting Lemma for complete graphs
- An \(L^p\) theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- Near-perfect clique-factors in sparse pseudorandom graphs
- Extremal cuts of sparse random graphs
- A counting lemma for binary matroids and applications to extremal problems
- Additive combinatorics and graph theory
- Diagonal Ramsey via effective quasirandomness
- Counting results for sparse pseudorandom hypergraphs. I.
This page was built for publication: Extremal results in sparse pseudorandom graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2445889)
