Convergence of graphs with intermediate density
From MaRDI portal
Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Density (toughness, etc.) (05C42) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Infinite graphs (05C63) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)
Abstract: We propose a notion of graph convergence that interpolates between the Benjamini--Schramm convergence of bounded degree graphs and the dense graph convergence developed by L'aszl'o Lov'asz and his coauthors. We prove that spectra of graphs, and also some important graph parameters such as numbers of colorings or matchings, behave well in convergent graph sequences. Special attention is given to graph sequences of large essential girth, for which asymptotics of coloring numbers are explicitly calculated. We also treat numbers of matchings in approximately regular graphs. We introduce tentative limit objects that we call graphonings because they are common generalizations of graphons and graphings. Special forms of these, called Hausdorff and Euclidean graphonings, involve geometric measure theory. We construct Euclidean graphonings that provide limits of hypercubes and of finite projective planes, and, more generally, of a wide class of regular sequences of large essential girth. For any convergent sequence of large essential girth, we construct weaker limit objects: an involution invariant probability measure on the sub-Markov space of consistent measure sequences (this is unique), or an acyclic reversible sub-Markov kernel on a probability space (non-unique). We also pose some open problems.
Recommendations
- Limits of dense graph sequences
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- On limits of sparse random graphs
- Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
Cites work
- Benjamini-Schramm continuity of root moments of graph polynomials
- Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
- Borel liftings of graph limits
- Chromatic roots and limits of dense graphs
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Functions of bounded variation, the derivative of the one dimensional maximal function, and applications to inequalities
- Hausdorff measure of homogeneous Cantor set
- scientific article; zbMATH DE number 428989 (Why is no real title available?)
- scientific article; zbMATH DE number 3824228 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 515978 (Why is no real title available?)
- scientific article; zbMATH DE number 1156633 (Why is no real title available?)
- scientific article; zbMATH DE number 1405497 (Why is no real title available?)
- scientific article; zbMATH DE number 3037624 (Why is no real title available?)
- Independent sets, matchings, and occupancy fractions
- Large networks and graph limits
- Limits of dense graph sequences
- Matching theory
- Matchings in Benjamini-Schramm convergent graph sequences
- Metrics for sparse graphs
- On limits of finite graphs
- On the asymptotic distribution of the zeros of Hermite, Laguerre, and Jonquière polynomials
- On the limit of large girth graph sequences
- Processes on unimodular random networks
- Sparse random graphs: eigenvalues and eigenvectors
- Sparse regular random graphs: spectral density and eigenvectors
- The expected eigenvalue distribution of a large regular graph
- The number of matchings in random regular graphs and bipartite graphs
- Theory of monomer-dimer systems
- Wigner matrices, the moments of roots of Hermite polynomials and the semicircle law
Cited in
(19)- A random graph of moderate density
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Measures on the square as sparse graph limits
- Limits of random trees. II
- Limits of locally-globally convergent graph sequences
- Weak convergence of finite graphs, integrated density of states and a Cheeger type inequality
- Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs
- Action convergence of operators and graphs
- Convergence theorems for graph sequences
- An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- Graph limits: An alternative approach to s‐graphons
- Subgraph densities in Markov spaces
- Random homomorphisms into the orthogonality graph
- On the limit of large girth graph sequences
- The matroid of a graphing
- The ineffectiveness of the regularity lemma for bounded degree graphs
- A compactification of the set of sequences of positive real numbers with applications to limits of graphs (extended abstract)
- Hyperfinite graph limits
This page was built for publication: Convergence of graphs with intermediate density
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604413)
