A Cheeger-type inequality on simplicial complexes (Q402582): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
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
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    combinatorial Hodge theory
    0 references
    discrete isoperimetry
    0 references
    spectral graph theory
    0 references