Gundert, Anna and Szedlak, May (2015). HIGHER DIMENSIONAL DISCRETE CHEEGER INEQUALITIES. J. Comput. Geom., 6 (2). S. 54 - 72. OTTAWA: CARLETON UNIV, DEPT MATHEMATICS & STATISTICS. ISSN 1920-180X
Full text not available from this repository.Abstract
For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of which states that lambda(G) <= h (G), where lambda(G) is the second smallest eigenvalue of the Laplacian of a graph G and h (G) is the Cheeger constant measuring the edge expansion of G. We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension (or uniform hypergraphs). Whereas higher dimensional Laplacians were introduced already in 1945 by Eckmann, the generalization of edge expansion to simplicial complexes is not straightforward. Recently, a topologically motivated notion analogous to edge expansion that is based on Z(2)-cohomology was introduced by Gromov and independently by Linial, Meshulam and Wallach. It is known that for this generalization there is no direct higher dimensional analogue of the lower bound of the Cheeger inequality. A different, combinatorially motivated generalization of the Cheeger constant, denoted by h(X), was studied by Parzanchevski, Rosenthal and Tessler. They showed that indeed lambda(X) <= h (X), where lambda(X) is the smallest non-trivial eigenvalue of the ((k - 1)-dimensional upper) Laplacian, for the case of k -dimensional simplicial complexes X with complete (k - 1)-skeleton. Whether this inequality also holds for k -dimensional complexes with non-complete (k - 1)-skeleton has been an open question. We give two proofs of the inequality for arbitrary complexes. The proofs differ strongly in the methods and structures employed, and each allows for a different kind of additional strengthening of the original result.
Item Type: | Journal Article | ||||||||||||
Creators: |
|
||||||||||||
URN: | urn:nbn:de:hbz:38-416228 | ||||||||||||
Journal or Publication Title: | J. Comput. Geom. | ||||||||||||
Volume: | 6 | ||||||||||||
Number: | 2 | ||||||||||||
Page Range: | S. 54 - 72 | ||||||||||||
Date: | 2015 | ||||||||||||
Publisher: | CARLETON UNIV, DEPT MATHEMATICS & STATISTICS | ||||||||||||
Place of Publication: | OTTAWA | ||||||||||||
ISSN: | 1920-180X | ||||||||||||
Language: | English | ||||||||||||
Faculty: | Unspecified | ||||||||||||
Divisions: | Unspecified | ||||||||||||
Subjects: | no entry | ||||||||||||
Uncontrolled Keywords: |
|
||||||||||||
URI: | http://kups.ub.uni-koeln.de/id/eprint/41622 |
Downloads
Downloads per month over past year
Export
Actions (login required)
View Item |