NDLI: Higher Dimensional Cheeger Inequalities

Please wait, while we are loading the content...

Counting and Enumerating Crossing-free Geometric Graphs

A Framework for Computing the Greedy Spanner

There are Plane Spanners of Maximum Degree 4

New and Improved Spanning Ratios for Yao Graphs

On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures

Progressive Geometric Algorithms

On the Impossibility of Dimension Reduction for Doubling Subsets of ℓp

The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems

Design of 3D printed mathematical art

Embeddability in the 3-sphere is decidable

The Connect-The-Dots Family of Puzzles: The Video

LiveCG: an Interactive Visualization Environment for Computational Geometry

Trajectory Grouping Structure: the Video

Visualizing hyperbolic Voronoi diagrams

Animation of an Algorithm for Drawing Graphs in 3D

Visualization of Floater and Gotsman's Morphing Algorithm

Geometric kth Shortest Paths: the Applet

Polytope Offsets and Straight Skeletons in 3D

Optimal Geometric Flows via Dual Programs

Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs

Outerstring graphs are χ-bounded

Improved bounds for the conflict-free chromatic art gallery problem

Linear transformation distance for bichromatic matchings

Delaunay triangulations with disconnected realization spaces

Eliminating Tverberg Points, I. An Analogue of the Whitney Trick

Higher Dimensional Cheeger Inequalities

Incidences between points and lines in R4: Extended Abstract

On triple intersections of three families of unit circles

Finding the Largest Disk Containing a Query Point in Logarithmic Time with Linear Storage

Smallest enclosing ball for probabilistic data

Peeling Potatoes Near-Optimally in Near-Linear Time

On the Complexity of Randomly Weighted Voronoi Diagrams

A Census of Plane Graphs with Polyline Edges

Polynomials vanishing on grids: The Elekes-Rónyai problem revisited

Using Convex Relaxations for Efficiently and Privately Releasing Marginals

Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Better embeddings for planar Earth-Mover Distance over sparse sets

Higher-Quality Tetrahedral Mesh Generation for Domains with Small Angles by Constrained Delaunay Refinement

On the reconstruction of convex sets from random normal measurements

Intersection of paraboloids and application to Minkowski-type problems

Efficient Random-Walk Methods for Approximating Polytope Volume

The Persistent Homology of Distance Functions under Random Projection

Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces

Computing Topological Persistence for Simplicial Maps

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Towards Expressive 3D Modeling: new challenges for geometric computing

Computing the Fréchet distance with shortcuts is NP-hard

The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

Light spanners for Snowflake Metrics

Continuously Flattening Polyhedra Using Straight Skeletons

Two-Point L1 Shortest Path Queries in the Plane

Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

Free Edge Lengths in Plane Graphs

Weight Balancing on Boundaries and Skeletons

Separation by Convex Pseudo-Circles

Euclidean Steiner Shallow-Light Trees

Measuring Distance between Reeb Graphs

Stochastic Convergence of Persistence Landscapes and Silhouettes

The Morse Theory of Čech and Delaunay Filtrations

Gromov-Hausdorff Approximation of Filament Structure Using Reeb-type Graph

Metric Embedding, Hyperbolic Space, and Social Networks

Sampling with Removal in LP-type Problems

Liftings and stresses for planar periodic frameworks

The Opaque Square

The JS-graphs of Join and Split Trees

Distinct distances on algebraic curves in the plane

Lower bounds on geometric Ramsey functions

Curves in Rd intersecting every hyperplane at most d + 1 times

Higher Dimensional Cheeger Inequalities

Content Provider	ACM Digital Library
Author	Gundert, Anna Szedlák, May
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 λ(G) ≤ h(G), where λ(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 Z2-cohomology was introduced by Gromov and independently by Linial, Meshulam and Wallach and by Newman and Rabinovich. It is known that for this generalization there is no 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 λ(X) ≤ h(X), where λ(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.
Starting Page	181
Ending Page	188
Page Count	8
File Format	PDF
ISBN	9781450325943
DOI	10.1145/2582112.2582118
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-06-08
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Eigenvalues Discrete cheeger inequality Laplacians Simplicial complexes Hypergraphs
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in