Szemerédi's lemma for the analyst

DOI10.1007/S00039-007-0599-6zbMATH Open1123.46020OpenAlexW2068571612WikidataQ105583448 ScholiaQ105583448MaRDI QIDQ879618FDOQ879618

Authors: Balázs Szegedy, László Lovász 

Publication date: 14 May 2007

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00039-007-0599-6

Recommendations

• Szemerédi's regularity lemma revisited
• An Abstract Szemerédi Regularity Lemma
• Szemerédi's regularity lemma via martingales

zbMATH Keywords

cut-normkernel operators on Hilbert spacesSzemerédi's regularity lemma

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Inner product spaces and their generalizations, Hilbert spaces (46C99)

Cited In (99)

• On the lower tail variational problem for random graphs
• Regular partitions of gentle graphs
• On replica symmetry of large deviations in random graphs
• Limits of kernel operators and the spectral regularity lemma
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Hypergraph limits: A regularity approach
• An Abstract Szemerédi Regularity Lemma
• Weighted exponential random graph models: scope and large network limits
• Regularity lemmas and combinatorial algorithms
• Ramsey properties of algebraic graphs and hypergraphs
• Beyond the expanders
• Compact graphings
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• The automorphism group of a graphon
• The cut metric for probability distributions
• Uniqueness of Banach space valued graphons
• Cut distance identifying graphon parameters over weak* limits
• Sampling perspectives on sparse exchangeable graphs
• The role of topology in large deviations
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• Cut-norm and entropy minimization over \(\text{weak}^{\ast}\) limits
• Differential calculus on graphon space
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• \(\Gamma\)-limit of the cut functional on dense graph sequences
• An analytic approach to stability
• Grothendieck-type inequalities in combinatorial optimization
• Action convergence of operators and graphs
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• σ-algebras for quasirandom hypergraphs
• Cut norm discontinuity of triangular truncation of graphons
• Poset limits can be totally ordered
• Moments of two-variable functions and the uniqueness of graph limits
• Weak regularity and finitely forcible graph limits
• On the variational problem for upper tails in sparse random graphs
• Mean-field and graph limits for collective dynamics models with time-varying weights
• Estimating and understanding exponential random graph models
• The large deviation principle for interacting dynamical systems on random graphs
• A relative Szemerédi theorem
• Compact orbit spaces in Hilbert spaces and limits of edge-colouring models
• Hereditary quasirandomness without regularity
• Relating the cut distance and the weak* topology for graphons
• Proof of a conjecture of V. Nikiforov
• Testing properties of graphs and functions
• Densities in large permutations and parameter testing
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• More on quasi-random graphs, subgraph counts and graph limits
• Szemerédi's regularity lemma via martingales
• A unified view of graph regularity via matrix decompositions
• The large deviation principle for the Erdős-Rényi random graph
• Emergent structures in large networks
• Quasi-random graphs and graph limits
• The quasi-randomness of hypergraph cut properties
• Linear embeddings of graphs and graph limits
• On regularity lemmas and their algorithmic applications
• Limits of functions on groups
• Limits of sparse configuration models and beyond: graphexes and multigraphexes
• On the chromatic number in the stochastic block model
• A hypergraph blow-up lemma
• Bounds for graph regularity and removal lemmas
• On derivatives of graphon parameters
• Non-deterministic graph property testing
• Sparse exchangeable graphs and their limits via graphon processes
• Singularities in the entropy of asymptotically large simple graphs
• Multipodal structure and phase transitions in large constrained graphs
• Finitely forcible graphons
• Phase transitions in finite random networks
• Compactness and finite forcibility of graphons
• Random graphons and a weak positivstellensatz for graphs
• Poset limits and exchangeable random posets
• Identifiability for graphexes and the weak kernel metric
• Limits of locally-globally convergent graph sequences
• Triforce and corners
• On the continuum limit of epidemiological models on graphs: convergence and approximation results
• Estimating parameters associated with monotone properties
• Typical large graphs with given edge and triangle densities
• Graphons arising from graphs definable over finite fields
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• Popular differences for corners in abelian groups
• On a question of Vera T. Sós about size forcing of graphons
• Limits of multi-relational graphs
• Maximum spread of graphs and bipartite graphs
• Limit theorems for exponential random graphs
• Testing versus estimation of graph properties, revisited
• On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
• Breaking of ensemble equivalence for dense random graphs under a single constraint
• Existence of a symmetric bipodal phase in the edge-triangle model
• Upper tail of the spectral radius of sparse Erdös-Rényi graphs
• A sparse regular approximation lemma
• Local-vs-global combinatorics
• Prominent examples of flip processes
• A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds
• Forcing quasirandomness with triangles
• An analytic approach to sparse hypergraphs: hypergraph removal
• A fast new algorithm for weak graph regularity
• Covariance loss, Szemeredi regularity, and differential privacy
• Continuous stable regularity
• Approximate real symmetric tensor rank
• Faster combinatorial \(k\)-clique algorithms
• The regularity method for graphs with few 4‐cycles

This page was built for publication: Szemerédi's lemma for the analyst

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879618)