A Cheeger-type inequality on simplicial complexes (Q402582): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Sayan Mukherjee / rank | |||
Normal rank | |||
Property / review text | |||
Let \(G\) be a graph with vertex set \(V\) and \(\delta S\) the set of edges connecting a vertex set \(S\) with a vertex in \(\overline{S}:= V-S\). The Cheeger number \(h\) is then defined by \[ h:= \min\limits_{\emptyset \subsetneq S \subsetneq V} \frac{|\delta S|}{\min \{|S|, |\overline{S}|\}}. \] The classical Cheeger inequality relates \(h\) to \(\lambda\), the second eigenvalue of the graph Laplacian, via the inequality \(\frac{h^2}{2\max\limits_{v\in V}d_v}\leq \lambda \leq 2h\). The goal of this paper is to study a possible generalization of the Cheeger inequality to simplicial complexes. The authors take great care to define all of the needed background for the generalizations, including the basics of (co)chain complexes and (co)chain homology groups, the \(k^{th}\) Lapalcian, and the Hamming norm. From these (co)chain complexes, a combinatorial Laplacian is derived. For the cochain complex, the authors are able to prove the non-existence of constants which would generalize the Cheeger inequality. However, the authors are able to prove a generalization in the chain complex case. If \(X\) is, for example, an \(m\)-dimensional orientable pseudomanifold, then \[ \frac{h_m^2}{2(m+1)}\leq \gamma_m\leq h_m \] where \(\gamma_m\) is an analogue of the spectral gap for dimension \(m\) on the chain complex and \(h_m\) the \(m\)-dimensional Cheeger number. The paper concludes with a discussion of how the results relate to graphs. | |||
Property / review text: Let \(G\) be a graph with vertex set \(V\) and \(\delta S\) the set of edges connecting a vertex set \(S\) with a vertex in \(\overline{S}:= V-S\). The Cheeger number \(h\) is then defined by \[ h:= \min\limits_{\emptyset \subsetneq S \subsetneq V} \frac{|\delta S|}{\min \{|S|, |\overline{S}|\}}. \] The classical Cheeger inequality relates \(h\) to \(\lambda\), the second eigenvalue of the graph Laplacian, via the inequality \(\frac{h^2}{2\max\limits_{v\in V}d_v}\leq \lambda \leq 2h\). The goal of this paper is to study a possible generalization of the Cheeger inequality to simplicial complexes. The authors take great care to define all of the needed background for the generalizations, including the basics of (co)chain complexes and (co)chain homology groups, the \(k^{th}\) Lapalcian, and the Hamming norm. From these (co)chain complexes, a combinatorial Laplacian is derived. For the cochain complex, the authors are able to prove the non-existence of constants which would generalize the Cheeger inequality. However, the authors are able to prove a generalization in the chain complex case. If \(X\) is, for example, an \(m\)-dimensional orientable pseudomanifold, then \[ \frac{h_m^2}{2(m+1)}\leq \gamma_m\leq h_m \] where \(\gamma_m\) is an analogue of the spectral gap for dimension \(m\) on the chain complex and \(h_m\) the \(m\)-dimensional Cheeger number. The paper concludes with a discussion of how the results relate to graphs. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Nicholas A. Scoville / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 55U10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05E45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 35P05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6335234 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
combinatorial Hodge theory | |||
Property / zbMATH Keywords: combinatorial Hodge theory / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
discrete isoperimetry | |||
Property / zbMATH Keywords: discrete isoperimetry / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
spectral graph theory | |||
Property / zbMATH Keywords: spectral graph theory / rank | |||
Normal rank |
Revision as of 17:42, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A Cheeger-type inequality on simplicial complexes |
scientific article |
Statements
A Cheeger-type inequality on simplicial complexes (English)
0 references
28 August 2014
0 references
Let \(G\) be a graph with vertex set \(V\) and \(\delta S\) the set of edges connecting a vertex set \(S\) with a vertex in \(\overline{S}:= V-S\). The Cheeger number \(h\) is then defined by \[ h:= \min\limits_{\emptyset \subsetneq S \subsetneq V} \frac{|\delta S|}{\min \{|S|, |\overline{S}|\}}. \] The classical Cheeger inequality relates \(h\) to \(\lambda\), the second eigenvalue of the graph Laplacian, via the inequality \(\frac{h^2}{2\max\limits_{v\in V}d_v}\leq \lambda \leq 2h\). The goal of this paper is to study a possible generalization of the Cheeger inequality to simplicial complexes. The authors take great care to define all of the needed background for the generalizations, including the basics of (co)chain complexes and (co)chain homology groups, the \(k^{th}\) Lapalcian, and the Hamming norm. From these (co)chain complexes, a combinatorial Laplacian is derived. For the cochain complex, the authors are able to prove the non-existence of constants which would generalize the Cheeger inequality. However, the authors are able to prove a generalization in the chain complex case. If \(X\) is, for example, an \(m\)-dimensional orientable pseudomanifold, then \[ \frac{h_m^2}{2(m+1)}\leq \gamma_m\leq h_m \] where \(\gamma_m\) is an analogue of the spectral gap for dimension \(m\) on the chain complex and \(h_m\) the \(m\)-dimensional Cheeger number. The paper concludes with a discussion of how the results relate to graphs.
0 references
combinatorial Hodge theory
0 references
discrete isoperimetry
0 references
spectral graph theory
0 references