From quasirandom graphs to graph limits and graphlets
From MaRDI portal
Abstract: We generalize the notion of quasirandom which concerns a class of equivalent properties that random graphs satisfy. We show that the convergence of a graph sequence under the spectral distance is equivalent to the convergence using the (normalized) cut distance. The resulting graph limit is called graphlets. We then consider several families of graphlets and, in particular, we characterize graphlets with low ranks for both dense and sparse graphs.
Recommendations
- On limits of sparse random graphs
- Quasi-random graphs and graph limits
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- More on quasi-random graphs, subgraph counts and graph limits
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
Cites work
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 3452971 (Why is no real title available?)
- scientific article; zbMATH DE number 3201991 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A Local Graph Partitioning Algorithm Using Heat Kernel Pagerank
- Complex graphs and networks
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Coverings, heat kernels and spanning trees
- Embedding Riemannian manifolds by their heat kernel
- Filling Riemannian manifolds
- Finitely forcible graphons
- Generalized quasirandom graphs
- Graph limits and exchangeable random graphs
- Graph norms and Sidorenko's conjecture
- Hermitian matrices and graphs: Singular values and discrepancy
- Large networks and graph limits
- Limits of dense graph sequences
- Limits of kernel operators and the spectral regularity lemma
- Moments of two-variable functions and the uniqueness of graph limits
- Monotone graph limits and quasimonotone graphs
- On limits of finite graphs
- On the spectra of general random graphs
- Quasi-Random Set Systems
- Quasi-random graphs
- Quasi‐random graphs with given degree sequences
- Quick approximation to matrices and applications
- Recurrence of distributional limits of finite planar graphs
- Regularity partitions and the topology of graphons
- Representations for partially exchangeable arrays of random variables
- Sparse graphs: metrics and random models
- Sparse quasi-random graphs
- Testing properties of graphs and functions
- Threshold graph limits and random threshold graphs
- Undecidability of linear inequalities in graph homomorphism densities
- Using discrepancy to control singular values for nonnegative matrices
- \(L^{2}\)-spectral invariants and convergent sequences of finite graphs
Cited in
(10)- A limit law of almost \(l\)-partite graphs
- Sharp spectral bounds of several graph parameters using eigenvector norms
- Matrix and discrepancy view of generalized random and quasirandom graphs
- Linear embeddings of graphs and graph limits
- Harmonic analysis on graphs via Bratteli diagrams and path-space measures
- Graph limits and exchangeable random graphs
- Eigenvalues and extremal degrees of graphs
- Monotone graph limits and quasimonotone graphs
- Characteristic power series of graph limits
- Generalized quasirandom properties of expanding graph sequences
This page was built for publication: From quasirandom graphs to graph limits and graphlets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402587)
