The first Cheeger constant of a simplex

DOI10.1007/S00373-017-1853-9MaRDI QIDQ1696541zbMATH OpenOpenAlexFDO

Authors Dmitry N. Kozlov

Publication date 14 February 2018

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.07136

zbMATH Keywords

Cheeger constantcoboundary expanderscohomologysimplicial complexes

Mathematics Subject Classification ID

Combinatorial aspects of simplicial complexes (05E45)

Abstract: The coboundary expansion generalizes the classical graph expansion to the case of the general simplicial complexes, and allows the definition of the higher-dimensional Cheeger constants $h_k(X)$ for an arbitrary simplicial complex $X$, and any $kgeq0$. In this paper we investigate the value of $h_1(Delt{a}^{[n]})$ - the first Cheeger constant of a simplex with $n$ vertices. It is known, due to the pioneering work of Meshulam and Wallach, that [lceil n/3 ceilgeq h_1(Delta^{[n]})geq n/3, extrm{ for all } n,] and that the equality $h_1(Delt{a}^{[n]})=n/3$ is achieved when $n$ is divisible by $3$. Here we expand on these results. First, we show that [h_1(Delta^{[n]})=n/3, extrm{ whenever }n extrm{ is not a power of }2.] So the sharp equality holds on a set whose density goes to $1$. Second, we show that [h_1(Delta^{[n]})=n/3+O(1/n), extrm{ when }n extrm{ is a power of }2.] In other words, as $n$ goes to infinity, the value $h_1(Delt{a}^{[n]})-n/3$ is either $0$ or goes to $0$ very rapidly. Our methods include recasting the original question in purely graph-theoretic language, followed by a detailed investigation of a specific graph family, the so-called {it staircase graphs}. These are defined by associating a graph to every partition, and appear to be especially suited to gain information about the first Cheeger constant of a simplex.

Recommendations

• Higher Dimensional Cheeger Inequalities
• Higher dimensional discrete Cheeger inequalities
• Quantitative aspects of acyclicity
• A Cheeger-type inequality on simplicial complexes
• Isoperimetric inequalities in simplicial complexes

Cites work

• Coboundary expanders
• Combinatorial algebraic topology
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Expansion of building-like complexes
• Homological connectivity of random k -dimensional complexes
• Homological connectivity of random 2-complexes
• Ramanujan complexes and high dimensional expanders
• Random Latin squares and 2-dimensional expanders
• Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry

Cited in

(1)

• Quantitative aspects of acyclicity

This page was built for publication: The first Cheeger constant of a simplex

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