Limits of locally-globally convergent graph sequences

DOI10.1007/S00039-014-0258-7zbMATH Open1294.05109OpenAlexW2163712938MaRDI QIDQ2453451FDOQ2453451

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

Publication date: 6 June 2014

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

Full work available at URL: https://doi.org/10.1007/s00039-014-0258-7

Recommendations

• Measures on the square as sparse graph limits
• On limits of sparse random graphs
• Convergence of graphs with intermediate density
• Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

zbMATH Keywords

Bernoulli graphingsBernoulli graphings,

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Graph theory (05C99)

Cites Work

• Limits of dense graph sequences
• Recurrence of distributional limits of finite planar graphs
• Large networks and graph limits
• Eigenvalues and expanders
• Moments of two-variable functions and the uniqueness of graph limits
• Title not available (Why is that?)
• Topics in orbit equivalence
• Processes on unimodular random networks
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Global aspects of ergodic group actions
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• A measure-theoretic approach to the theory of dense hypergraphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Left and right convergence of graphs with bounded degree
• Bernoulli actions are weakly contained in any free action
• Szemerédi's lemma for the analyst
• Sparse graphs: metrics and random models
• Limits of local algorithms over sparse random graphs
• On limits of finite graphs
• Borel oracles. An analytical approach to constant-time algorithms
• Borel chromatic numbers
• Non-deterministic graph property testing
• Local Graph Partitions for Approximation and Testing
• Every minor-closed property of sparse graphs is testable
• Finite graphs and amenability
• Hyperfinite graph limits
• The combinatoral cost

Cited In (39)

• Algorithmic obstructions in the random number partitioning problem
• Unimodular measures on the space of all Riemannian manifolds
• Optimal low-degree hardness of maximum independent set
• Kőnig's line coloring and Vizing's theorems for graphings
• Compact graphings
• First-Order Convergence and Roots
• Multiplication of weak equivalence classes may be discontinuous
• Convergence theorems for graph sequences
• Suboptimality of local algorithms for a class of max-cut problems
• Local approximation of the maximum cut in regular graphs
• Ramanujan graphings and correlation decay in local algorithms
• Factor of iid percolation on trees
• Flows on measurable spaces
• Action convergence of operators and graphs
• Subgraph densities in a surface
• Uniform rank gradient, cost, and local-global convergence
• First order convergence of matroids
• Local-global convergence, an analytic and structural approach
• Graph limits: An alternative approach to s‐graphons
• Measures on the square as sparse graph limits
• A short proof of the equivalence of left and right convergence for sparse graphs
• Ergodic theorems for the shift action and pointwise versions of the Abért-Weiss theorem
• Performance of sequential local algorithms for the random NAE-\(K\)-SAT problem
• Examples in the entropy theory of countable group actions
• Invariant Schreier decorations of unimodular random networks
• Non-standard limits of graphs and some orbit equivalence invariants
• Greedy maximal independent sets via local limits
• Spectral measures of factor of i.i.d. processes on vertex-transitive graphs
• Graph theory -- a survey on the occasion of the Abel Prize for László Lovász
• Pointwise ergodic theorem for locally countable quasi-pmp graphs
• Typicality and entropy of processes on infinite trees
• A determinacy approach to Borel combinatorics
• On the almost eigenvectors of random regular graphs
• First order limits of sparse graphs: plane trees and path-width
• On a curious problem and what it lead to
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• Hyperfinite graphings and combinatorial optimization
• Weak containment of measure-preserving group actions
• Finding one community in a sparse graph

This page was built for publication: Limits of locally-globally convergent graph sequences

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