Algebraic and combinatorial expansion in random simplicial complexes

DOI10.1002/RSA.21036MaRDI QIDQ6074688zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Michał Przykucki

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2006.09445, https://research.birmingham.ac.uk/portal/en/publications/algebraic-and-combinatorial-expansion-in-random-simplicial-complexes(2560c904-c337-4fc5-b8df-c89e8f54e459).html

zbMATH Keywords

Cheeger constantconductanceLaplace operatorrandom simplicial complexes

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Symmetric functions and generalizations (05E05) Combinatorial aspects of simplicial complexes (05E45) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: In this paper we consider the expansion properties and the spectrum of the combinatorial Laplace operator of a $d$-dimensional Linial-Meshulam random simplicial complex, above the cohomological connectivity threshold. We consider the spectral gap of the Laplace operator and the Cheeger constant as this was introduced by Parzanchevski, Rosenthal and Tessler ($Combinatorica$ 36, 2016). We show that with high probability the spectral gap of the random simplicial complex as well as the Cheeger constant are both concentrated around the minimum co-degree of among all $d-1$-faces. Furthermore, we consider a generalisation of a random walk on such a complex and show that the associated conductance is with high probability bounded away from 0.

Recommendations

• Exponential random simplicial complexes
• Random Simplicial Complexes
• Random Simplicial Complexes: Models and Phenomena
• Simplicial homology of random configurations
• Random simplicial complexes, duality and the critical dimension
• Homology of multi-parameter random simplicial complexes
• The combinatorial structure of random polytopes
• Large random simplicial complexes. I
• Spectral expansion of random sum complexes
• Homological domination in large random simplicial complexes

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Approximating the Permanent
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalue confinement and spectral gap for random simplicial complexes
• Eigenvalues and expanders
• Expanding graphs contain all small trees
• Explicit construction of linear sized tolerant networks
• Extremal eigenvalues of critical Erdős-Rényi graphs
• Harmonic functions and boundary value problems on a chain complex
• Higher dimensional discrete Cheeger inequalities
• Homological connectivity of random 2-complexes
• Homological connectivity of random k -dimensional complexes
• scientific article; zbMATH DE number 3173143 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (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?)
• Inside the critical window for cohomology of random \(k\)-complexes
• Integral homology of random simplicial complexes
• Isoperimetric inequalities in simplicial complexes
• Large random simplicial complexes. I
• Large random simplicial complexes. II: The fundamental group
• Large random simplicial complexes. III: The critical dimension.
• Mixing in high-dimensional expanders
• On the Laplacian Eigenvalues of G_n,p
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Random Graphs
• Random Simplicial Complexes
• Simplicial complexes: spectrum, homology and random walks
• Spectra of combinatorial Laplace operators on simplicial complexes
• Spectral gaps of random graphs and applications
• Spectral norm of random matrices
• Spectral radii of sparse random matrices
• Spectral techniques applied to sparse random graphs
• The dimension-free structure of nonhomogeneous random matrices
• The eigenvalues of random symmetric matrices
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Spectra of Random Graphs with Given Expected Degrees
• The threshold for integer homology in random \(d\)-complexes

Cited in

(5)

• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Normalized Hodge Laplacian matrix and application to random walk on simplicial complexes
• Eigenvalues and spectral gap in sparse random simplicial complexes
• Central limit theorem for linear eigenvalue statistics of the adjacency matrices of random simplicial complexes
• On the spectrum of random simplicial complexes in thermodynamic regime

This page was built for publication: Algebraic and combinatorial expansion in random simplicial complexes

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