Edge isoperimetric inequalities for product graphs

DOI10.1016/S0012-365X(99)00189-2MaRDI QIDQ1970722zbMATH OpenOpenAlexWikidataFDO

Authors Jean-Pierre Tillich

Publication date 26 April 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00189-2

zbMATH Keywords

edge-isoperimetric inequalityisoperimetric sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (05C99)

Review text

Let \({\mathcal F}\) be a function such that \(|\partial\Omega|> {\mathcal F}(|\Omega|)\) for every nonempty subset \(\Omega\) of \(V(G)\), where \(\partial\Omega\) denotes the set of edges of the graph connecting vertices of \(\Omega\) with the complement \(V\setminus\Omega\). Then \({\mathcal F}\) is called an edge-isoperimetric inequality and \(\partial\Omega\) is named the boundary of \(\Omega\). The author obtains such inequalities which are sharp for certain types of subsets called isoperimetric sets (sets of given size which have the smallest edge-boundary). Using a simple equivalence between isoperimetric inequalities and certain analytic inequalities in Riemannian manifolds [\textit{O. S. Rothaus}, J. Funct. Anal. 64, 296-313 (1985; Zbl 0578.46028)], the author proves the following theorem for product graphs: Let \(\ell(G)\) be the minimum of \(|\partial\Omega|/ |\Omega|\ln(|V|/ |\Omega|)\) over all nonempty subsets \(\Omega\) of \(V(G)\). Then \(\ell(G)= \ell(G^n)\) for any Cartesian power \(G^n\).

Recommendations

• General edge-isoperimetric inequalities. I: Information-theoretical methods
• scientific article; zbMATH DE number 2044916
• Isoperimetric Inequalities for Cartesian Products of Graphs
• Isoperimetric inequalities for graphs
• Isoperimetric numbers of graphs

Cited in

(19)

• Isoperimetric inequalities for Riemannian products
• Isoperimetric inequalities for graphs
• An inequality on the size of a set in a Cartesian product
• Edge-isoperimetric problems for Cartesian powers of regular graphs
• Gradient flows in metric random walk spaces
• The total variation flow in metric random walk spaces
• Lexicographic product and isoperimetric number
• Isoperimetric estimates in products
• Random Subgraphs in Sparse Graphs
• Isoperimetric Inequalities for Cartesian Products of Graphs
• scientific article; zbMATH DE number 2044916 (Why is no real title available?)
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• scientific article; zbMATH DE number 5049609 (Why is no real title available?)
• The giant component after percolation of product graphs
• Iterative solution of spatial network models by subspace decomposition
• The boundary of a graph and its isoperimetric inequality
• Nonlocal Perimeters and Curvature Flows on Graphs with Applications in Image Processing and High-Dimensional Data Classification
• Triangle Inequalities Indexed by Graphs
• Expansion and isoperimetric constants for product graphs

This page was built for publication: Edge isoperimetric inequalities for product graphs

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