A Cheeger-type inequality on simplicial complexes (Q402582): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(8 intermediate revisions by 6 users not shown) | |||
Property / author | |||
Property / author: Caroline J. Klivans / rank | |||
Property / author | |||
Property / author: Sayan Mukherjee / rank | |||
Property / author | |||
Property / author: Sayan Mukherjee / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Caroline J. Klivans / 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 | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56905934 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963986398 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1209.5091 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eigenvalues and expanders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Towards a theoretical foundation for Laplacian-based manifold methods / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871782 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3870040 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5614192 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5691133 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Random walks and local cuts in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal homologous cycles, total unimodularity, and linear programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: COBOUNDARY EXPANDERS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Simplicial matrix-tree theorems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Harmonic functions and boundary value problems on a chain complex / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5682350 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cluster algebras and triangulated surfaces. I: Cluster complexes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On eigenvalues of random complexes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Expander graphs and their applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On clusterings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homological connectivity of random 2-complexes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homological connectivity of random <i>k</i> -dimensional complexes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Isoperimetric numbers of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Isoperimetric inequalities in simplicial complexes / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 23:38, 8 July 2024
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
0 references