On the isoperimetric spectrum of graphs and its approximations

DOI10.1016/J.JCTB.2010.01.002zbMATH Open1203.05063arXiv0801.0278OpenAlexW2138300049MaRDI QIDQ974467FDOQ974467

Hossein Hajiabolhassan, Ramin Javadi, Amir Daneshgar

Publication date: 3 June 2010

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In this paper we consider higher isoperimetric numbers of a (finite directed) graph. In this regard we focus on the $n$th mean isoperimetric constant of a directed graph as the minimum of the mean outgoing normalized flows from a given set of $n$ disjoint subsets of the vertex set of the graph. We show that the second mean isoperimetric constant in this general setting, coincides with (the mean version of) the classical Cheeger constant of the graph, while for the rest of the spectrum we show that there is a fundamental difference between the $n$th isoperimetric constant and the number obtained by taking the minimum over all $n$-partitions. In this direction, we show that our definition is the correct one in the sense that it satisfies a Federer-Fleming-type theorem, and we also define and present examples for the concept of a supergeometric graph as a graph whose mean isoperimetric constants are attained on partitions at all levels. Moreover, considering the $$-completeness of the isoperimetric problem on graphs, we address ourselves to the approximation problem where we prove general spectral inequalities that give rise to a general Cheeger-type inequality as well. On the other hand, we also consider some algorithmic aspects of the problem where we show connections to orthogonal representations of graphs and following J.~Malik and J.~Shi ($2000$) we study the close relationships to the well-known $k$-means algorithm and normalized cuts method.

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

Recommendations

• Approximating the isoperimetric number of strongly regular graphs
• Isoperimetric Partitioning: A New Algorithm for Graph Partitioning
• Isoperimetric numbers of graphs
• On the complexity of isoperimetric problems on trees
• Computing the isoperimetric number of a graph

zbMATH Keywords

graphMarkov chainconnectivityisoperimetric numberCheeger type inequality

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Title not available (Why is that?)
• Chromatic number and the 2-rank of a graph
• Title not available (Why is that?)
• Potential theory on infinite networks
• Eigenspaces of graphs
• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Graph homomorphisms through random walks
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Isoperimetric numbers of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture
• Geometry and spectra of compact Riemann surfaces
• Laplacians and the Cheeger inequality for directed graphs
• Clustering large graphs via the singular value decomposition
• Perron-Frobenius type results and discrete versions of nodal domain theorems
• Sensitivity analysis of all eigenvalues of a symmetric matrix
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discrete nodal domain theorems
• On eigenfunctions of Markov processes on trees
• Title not available (Why is that?)
• Open problems of Paul Erd�s in graph theory
• Circular colouring and algebraic no-homomorphism theorems
• Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs
• Analytic inequalities, isoperimetric inequalities and logarithmic Sobolev inequalities
• Title not available (Why is that?)
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• A discrete nodal domain theorem for trees
• Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems
• Some geometric aspects of graphs and their eigenfunctions
• Courant's Nodal Line Theorem and Its Discrete Counterparts
• Isoperimetric properties of higher eigenvalues of elliptic operators
• Isoperimetric invariants for product Markov chains and graph products
• \(\lambda_{\infty}\), vertex isoperimetry and concentration
• Graph homomorphisms and nodal domains

Cited In (17)

• The isoperimetric and Kazhdan constants associated to a Paley graph
• Multi-way sparsest cut problem on trees with a control on the number of parts and outliers
• Nodal domain theorems for \(p\)-Laplacians on signed graphs
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Isospectral graph reductions and improved estimates of matrices' spectra
• Computing the isoperimetric number of a graph
• A competitive optimization approach for data clustering and orthogonal non-negative matrix factorization
• Approximating the isoperimetric number of strongly regular graphs
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• On the complexity of isoperimetric problems on trees
• Mean isoperimetry with control on outliers: exact and approximation algorithms
• Higher Cheeger ratios of features in Laplace-Beltrami eigenfunctions
• Isoperimetric inequalities, growth, and the spectrum of graphs
• The isospectral problem in graph theory
• Nonconvex weak sharp minima on Riemannian manifolds
• An isoperimetric constant for signed graphs
• Clustering and outlier detection using isoperimetric number of trees

This page was built for publication: On the isoperimetric spectrum of graphs and its approximations

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