Szemerédi’s Lemma for the Analyst

By L. Lov'asz, Balázs Szegedy. 2007

299 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/7ac79c852c43d367dd604bb8277be1d1f05afd1d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

The large deviation principle for the Erd\H{o}s-R\'enyi random graph (2010, background): “In a sequence of papers [5, 6, 7, 15, 19, 20, 21, 22, 23, 24, 25] Laszlo Lovász with coauthors (listed here in order of frequency) V.”
Mean-field and graph limits for collective dynamics models with time-varying weights (2020, unknown): “In 2014, Medvedev used techniques from the recent theory of graph limit [5, 4, 19, 20, 18] to derive rigorously the continuum limit of dynamical models on deterministic graphs [22].”
Graph limits and exchangeable random graphs (2007, background): “It is natural to seek an approximation theory: What does it mean for a sequence of graphs to converge? When can a large complex graph be approximated by a small graph? In a sequence of papers [6, 7, 8, 9, 15, 18, 19, 20, 23, 22, 24, 21], Laszlo Lovász with coauthors (listed here in order of frequenc”
Estimating and understanding exponential random graph models (2011, background): “(Minimizers exist due to the Lovász–Szegedy compactness theorem [41], Theorem 5.”
Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, background): “It was proved in [28] that the metric space (W[0,1], δ ) is compact.”
Matrix estimation by Universal Singular Value Thresholding (2012, background): “ Graphons. A graphon is a measurable function f: [0;1]2 ![0;1] that satises f(x;y) f(y;x). The term ‘graphon’ was coined by Lovasz and coauthors in the growing literature on limits of dense graphs [21, 22, 23, 72, 73, 74]. Such functions also arise in the related study of weakly exchangeable random ”
Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “2 of [127]): let h( , r) > 0 be an arbitrary fixed function; then for any there is m = m( ) such that any graphon W can be written as W = U + A + B, where U is a step function with r ≤ m steps, ‖A‖2 ≤ h( , r) and ‖B‖1 ≤ .”
Counting Graph Homomorphisms (2006, background): “In other words, attaching g0 at two nodes is effectively the same as identifying the two nodes (this is why it is called a “contractor” in [45]).”
Limits of locally–globally convergent graph sequences (2012, background): “For example the theory of dense graph limits [25, 26, 11] works well if the number of edges is quadratic in the number of vertices but it trivializes for sparser graphs.”
An $L^{p}$ theory of sparse graph convergence II: LD convergence, quotients and right convergence (2014, background): “where the infimum is over all invertible maps φ : [0,1] → [0,1] such that both φ and its inverse are measure preserving, and W is defined by W(x, y) = W(φ(x),φ(y)) (see [7, 8, 12]); such a map φ is called a measure-preserving bijection.”
Graphons, cut norm and distance, couplings and rearrangements (2010, background): “) The compactness is closely related to Szemerédi’s regularity lemma, see [49].”
An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications (2010, background): “See also [40] for a related analytical perspective on the regularity lemma.”
The chromatic thresholds of graphs (2011, background): “The lemma has turned out to have an enormous number of applications, and many important extensions and variations have been proved (see for example [17, 23, 29, 34] and the references therein).”