Extremal results in sparse pseudorandom graphs
From MaRDI portal
Publication:2445889
DOI10.1016/j.aim.2013.12.004zbMath1285.05096arXiv1204.6645OpenAlexW2159703794WikidataQ105583626 ScholiaQ105583626MaRDI QIDQ2445889
David Conlon, Yufei Zhao, Jacob Fox
Publication date: 15 April 2014
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.6645
extremal combinatoricsSzemerédi's regularity lemmasparse graphscounting lemmasparse regularity lemmagraph removal lemma
Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)
Related Items
Polynomial configurations in subsets of random and pseudo-random sets, A counterexample to the Bollobás–Riordan conjectures on sparse graph limits, Additive combinatorics and graph theory, Counting in hypergraphs via regularity inheritance, A counting lemma for sparse pseudorandom hypergraphs, On replica symmetry of large deviations in random graphs, A new proof of the KŁR conjecture, Counting results for sparse pseudorandom hypergraphs. I., Diagonal Ramsey via effective quasirandomness, Finding any given 2‐factor in sparse pseudorandom graphs efficiently, Turán numbers of bipartite graphs plus an odd cycle, A unified view of graph regularity via matrix decompositions, Factors and loose Hamilton cycles in sparse pseudo‐random hypergraphs, A Sequence of Triangle-Free Pseudorandom Graphs, On the KŁR conjecture in random graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, FORCING QUASIRANDOMNESS WITH TRIANGLES, An analytic approach to sparse hypergraphs: hypergraph removal, Powers of Hamilton cycles in pseudorandom graphs, A weighted regularity lemma with applications, Near-perfect clique-factors in sparse pseudorandom graphs, On two-point configurations in subsets of pseudo-random sets, Arithmetic progressions, different regularity lemmas and removal lemmas, An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions, Discrepancy and eigenvalues of Cayley graphs, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, The regularity method for graphs with few 4‐cycles, A relative Szemerédi theorem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The clique density theorem
- Extremal results for random discrete structures
- Combinatorial theorems in sparse random sets
- On the KŁR conjecture in random graphs
- Extremal results for odd cycles in sparse pseudorandom graphs
- Hypergraph containers
- An approximate version of Sidorenko's conjecture
- Sparse partition universal graphs for graphs of bounded degree
- A new proof of the graph removal lemma
- A new upper bound for diagonal Ramsey numbers
- The Ramsey number of a graph with bounded maximum degree
- Induced-universal graphs for graphs with bounded maximum degree
- A variant of the hypergraph removal lemma
- Small subsets inherit sparse \(\varepsilon\)-regularity
- Limits of dense graph sequences
- Lifts, discrepancy and nearly optimal spectral gap
- Turán's theorem for pseudo-random graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- A combinatorial proof of the removal lemma for groups
- Two remarks on the Burr-Erdős conjecture
- Explicit Ramsey graphs and orthonormal labelings
- Lower bounds of tower type for Szemerédi's uniformity lemma
- Approximating the independence number via the \(\vartheta\)-function
- On \(K^ 4\)-free subgraphs of random graphs
- Sparse quasi-random graphs
- Embedding graphs with bounded degree in sparse pseudorandom graphs
- Turán's extremal problem in random graphs: Forbidding even cycles
- On induced Ramsey numbers for graphs with bounded maximum degree
- Bounds for graph regularity and removal lemmas
- A correlation inequality for bipartite graphs
- The primes contain arbitrarily long arithmetic progressions
- Additive approximation for edge-deletion problems
- Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
- Hypergraph regularity and the multidimensional Szemerédi theorem
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Szemerédi's Regularity Lemma for Matrices and Sparse Graphs
- An Efficient Sparse Regularity Concept
- Ramsey properties of random discrete structures
- Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
- The number of cliques in graphs of given order and size
- On Sets of Acquaintances and Strangers at any Party
- Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs
- On the Minimal Density of Triangles in Graphs
- Explicit Construction of Small Folkman Graphs
- Quasirandom Groups
- On the Folkman Numberf(2, 3, 4)
- A Disproof of a Conjecture of Erdős in Ramsey Theory
- Cutting a graph into two dissimilar halves
- On the Ramsey multiplicities of graphs—problems and recent results
- On sets of integers containing k elements in arithmetic progression
- The Algorithmic Aspects of the Regularity Lemma
- Szemerédi’s Regularity Lemma for Sparse Graphs
- Regular pairs in sparse random graphs I
- On graphs with linear Ramsey numbers
- Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
- Quasi-Random Set Systems
- Regularity Lemma for k-uniform hypergraphs
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Threshold Functions for Ramsey Properties
- Independent sets in hypergraphs
- A probabilistic counting lemma for complete graphs
- Quasi‐random graphs with given degree sequences
- There exist graphs with super‐exponential Ramsey multiplicity constant
- A generalization of Turán's theorem
- The counting lemma for regular k‐uniform hypergraphs
- Approximating the Cut-Norm via Grothendieck's Inequality
- Imbalances in k‐colorations
- A Spectral Turán Theorem
- On the structure of linear graphs
- Quasi-random graphs
- Induced Ramsey-type theorems
- Efficient testing of large graphs