Pull-push method: a new approach to edge-isoperimetric problems

DOI10.1016/J.DISC.2023.113632MaRDI QIDQ6056726zbMATH OpenOpenAlexFDO

Authors Sergej L. Bezrukov, Nikola Kuzmanovski, Jounglag Lim

Publication date 4 October 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Cartesian poweredge-isoperimetricinequalityisoperimetriclocal-global principlepull-push method

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: We prove a generalization of the Ahlswede-Cai local-global principle. A new technique to handle edge-isoperimetric problems is introduced which we call the pull-push method. Our main result includes all previously published results in this area as special cases with the only exception of the edge-isoperimetric problem for grids. With this we partially answer a question of Harper on local-global principles. We also describe a strategy for further generalization of our results so that the case of grids would be covered, which would completely settle Harper's question.

Recommendations

• General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions
• On an isoperimetric problem for Hamming graphs
• General edge-isoperimetric inequalities. I: Information-theoretical methods
• On partitioning of hypergraphs
• scientific article; zbMATH DE number 2060183

Cites work

• A note on edge isoperimetric numbers and regular graphs
• A note on the edges of the n-cube
• An edge-isoperimetric problem for powers of the Petersen graph
• Assignment of Numbers to Vertices
• Edge isoperimetric theorems for integer point arrays
• Edge-isoperimetric inequalities in the grid
• Edge-isoperimetric problems for Cartesian powers of regular graphs
• General edge-isoperimetric inequalities. I: Information-theoretical methods
• General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions
• scientific article; zbMATH DE number 1303526 (Why is no real title available?)
• scientific article; zbMATH DE number 2060183 (Why is no real title available?)
• Maximally Connected Arrays on the n-Cube
• New infinite family of regular edge-isoperimetric graphs
• On an equivalence in discrete extremal problems
• Optimal Assignments of Numbers to Vertices
• The edge-isoperimetric problem for discrete tori

Cited in

(2)

• Reflect-push methods. Part I: Two dimensional techniques
• Towards a complete local-global principle

This page was built for publication: Pull-push method: a new approach to edge-isoperimetric problems

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