A Cheeger cut for uniform hypergraphs

DOI10.1007/S00373-021-02348-ZMaRDI QIDQ2053692zbMATH OpenOpenAlexFDO

Authors R. Mulas

Publication date 30 November 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2011.06816

zbMATH Keywords

Cheeger inequalitieshypergraphsnormalized Laplacianspectral clustering

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The graph Cheeger constant and Cheeger inequalities are generalized to the case of hypergraphs whose edges have the same cardinality. In particular, it is shown that the second largest eigenvalue of the generalized normalized Laplacian is bounded both above and below by the generalized Cheeger constant, and the corresponding eigenfunctions can be used to approximate the Cheeger cut.

Recommendations

• Spectral properties of hypergraph Laplacian and approximation algorithms
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• A generalized Cheeger inequality
• Many sparse cuts via higher eigenvalues

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A note on the isoperimetric constant
• An oriented hypergraphic approach to algebraic graph theory
• Consistency of spectral clustering
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• scientific article; zbMATH DE number 3673238 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Hypergraph Laplace operators for chemical reaction networks
• Isoperimetric Inequalities in Mathematical Physics. (AM-27)
• Minimal embedding dimensions of connected neural codes
• On the spectrum of hypergraphs
• Sharp bounds for the largest eigenvalue
• SIS epidemic propagation on hypergraphs
• Spectral partitioning works: planar graphs and finite element meshes
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Spectral theory of Laplace operators on oriented hypergraphs
• Stochastic dynamics on hypergraphs and the spatial majority rule model
• The 1-Laplacian Cheeger cut: theory and algorithms
• The normalized graph cut and Cheeger constant: from discrete to continuous

Cited in

(19)

• On uniform \(f\)-vectors of cutsets in the truncated Boolean lattice
• Estimating cellular redundancy in networks of genetic expression
• Random walks and Laplacians on hypergraphs: when do they match?
• Finding Cheeger cuts in hypergraphs via heat equation
• Optimal Cheeger cuts and bisections of random geometric graphs
• The trace and Estrada index of uniform hypergraphs with cut vertices
• A generalized Cheeger inequality
• Cheeger inequalities for general edge-weighted directed graphs
• A Cheeger inequality of a distance regular graph using Green's function
• Spectral properties of hypergraph Laplacian and approximation algorithms
• Multi-way dual Cheeger constants and spectral bounds of graphs
• The normalized graph cut and Cheeger constant: from discrete to continuous
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• Hypergraph Cuts with General Splitting Functions
• Cheeger inequalities for submodular transformations
• Normalized Laplacian eigenvalues of hypergraphs
• Coloring outside the lines: spectral bounds for generalized hypergraph colorings
• Distributional limits of graph cuts on discretized grids
• A note on Cheeger inequalities for uniform hypergraphs

This page was built for publication: A Cheeger cut for uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2053692)