Generalized quasirandom properties of expanding graph sequences
From MaRDI portal
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Applications of graph theory (05C90) Classification and discrimination; cluster analysis (statistical aspects) (62H30)
Abstract: We consider special multiclass spectral, discrepancy, degree, and codegree properties of expanding graph sequences. As we can prove equivalences and implications between them and the definition of the generalized quasirandomness of Lov'asz--S'os (2008), they can be regarded as generalized quasirandom properties akin to the equivalent quasirandom properties of the seminal Chung--Graham--Wilson paper (1989) in the one-class scenario. Since these properties are valid for certain deterministic graph sequences, irrespective of stochastic models, the partial implications also justify for law-dimensional embedding of large-scale graphs and for discrepancy minimizing spectral clustering.
Recommendations
Cites work
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Dense expanders and pseudo-random bipartite graphs
- Discrepancy minimizing spectral clustering
- Eigenvalues and expanders
- Eigenvalues and partitionings of the edges of a graph
- Expander graphs and their applications
- Finding Planted Partitions in Random Graphs with General Degree Distributions
- Generalized quasirandom graphs
- Geometric bounds for eigenvalues of Markov chains
- scientific article; zbMATH DE number 4027516 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- Isoperimetric inequalities, growth, and the spectrum of graphs
- Limits of kernel operators and the spectral regularity lemma
- Mixing properties and the chromatic number of Ramanujan complexes
- Modularity spectra, eigen-subspaces, and structure of weighted graphs
- Networks. An introduction.
- On the concentration of eigenvalues of random symmetric matrices
- Quasi-random graphs
- Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
- Quasi‐random graphs with given degree sequences
- Quick approximation to matrices and applications
- Random graphs.
- Recognizing linear structure in noisy matrices
- Reconstruction and estimation in the planted partition model
- Relating multiway discrepancy and singular values of nonnegative rectangular matrices
- Singular value decomposition of large random matrices (for two-way classification of microarrays)
- Spectral clustering and biclustering. Learning large graphs and contingency tables
- Szemerédi's partition and quasirandomness
- Testability of minimum balanced multiway cut densities
- The effectiveness of Lloyd-type methods for the \(k\)-means problem
- The phase transition in inhomogeneous random graphs
- Turán's theorem for pseudo-random graphs
Cited in
(2)
This page was built for publication: Generalized quasirandom properties of expanding graph sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5216273)
