Edge isoperimetric theorems for integer point arrays

DOI10.1016/0893-9659(95)00015-IMaRDI QIDQ1893693zbMATH OpenFDO

Authors Sergej L. Bezrukov, Rudolf Ahlswede

Publication date 20 July 1995

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0893-9659(95)00015-I

zbMATH Keywords

Cartesian productgridpaths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

The authors consider \(m\)-vertex subsets of the Cartesian product of \(n\) paths and those of them which have maximal number of induced edges of the grid and those which are separable from their complement by the least number of edges. They generalize and extend results of \textit{B. Bollobás} and \textit{I. Leader} [Edge-isoperimetric inequalities in the grid, Combinatorica 11, No. 4, 299-314 (1991; Zbl 0755.05045)].

Recommendations

• Edge-isoperimetric inequalities in the grid
• The edge-isoperimetric problem for discrete tori
• scientific article; zbMATH DE number 1303526
• Edge-Isoperimetric Inequalities and Influences
• Remarks on an Edge Isoperimetric Problem
• scientific article; zbMATH DE number 2188353
• scientific article; zbMATH DE number 2044916
• Edge-isoperimetric problems for Cartesian powers of regular graphs
• Edge isoperimetric inequalities for powers of the hypercube
• The isoperimetric number of \(d\)-dimensional \(k\)-ary arrays

Cites work

• A necessary condition on minimal cube numberings
• Assignment of Numbers to Vertices
• Edge-isoperimetric inequalities in the grid
• Graphs with maximal number of adjacent pairs of edges
• Optimal Assignments of Numbers to Vertices

Cited in

(20)

• On an equivalence in discrete extremal problems
• On \(k\)-ary \(n\)-cubes: Theory and applications.
• A new lower bound for the bipartite crossing number with applications
• Edge-isoperimetric problems for Cartesian powers of regular graphs
• Maximal fluctuations around the Wulff shape for edge-isoperimetric sets in \({\mathbb{Z}}^d \): a sharp scaling law
• A Counterexample to Kleitman's Conjecture Concerning an Edge-Isoperimetric Problem
• Vertex isoperimetric parameter of a computation graph
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• The isoperimetric number of \(d\)-dimensional \(k\)-ary arrays
• Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem
• scientific article; zbMATH DE number 2230265 (Why is no real title available?)
• Efficient embeddings of grids into grids
• Pull-push method: a new approach to edge-isoperimetric problems
• An extremal graph problem on a grid and an isoperimetric problem for polyominoes
• Reflect-push methods. Part I: Two dimensional techniques
• Macaulay posets and rings
• Towards a complete local-global principle
• The carving-width of generalized hypercubes
• Exact face-isoperimetric inequalities
• Escaping offline searchers and isoperimetric theorems

This page was built for publication: Edge isoperimetric theorems for integer point arrays

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