Edge-isoperimetric inequalities in the grid

DOI10.1007/BF01275667zbMath0755.05045OpenAlexW2093126960MaRDI QIDQ1181010

Publication date: 27 June 1992

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01275667

zbMATH Keywords

lower bound grid graph edge-isoperimetric inequalities

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial inequalities (05A20)

Related Items

Edge isoperimetric inequalities for powers of the hypercube, Planar lattice subsets with minimal vertex boundary, Concentration inequalities for log-concave distributions with applications to random surface fluctuations, Network decontamination with a single agent, Edge-isoperimetric problems for Cartesian powers of regular graphs, Edge isoperimetric theorems for integer point arrays, Sums in the grid, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Fractal graphs by iterated substitution, Variable neighborhood search for the vertex separation problem, Symmetry breaking in two-dimensional square grids: persistence and failure of the dimensional crossover, Isoperimetry, stability, and irredundance in direct products, On the number of hypercubic bipartitions of an integer, Random-field random surfaces, Pull-push method: a new approach to edge-isoperimetric problems, Isoperimetric stability in lattices, Large Monochromatic Components in Two-colored Grids, Graph coloring with no large monochromatic components, Probabilistic analysis of optimization problems on sparse random shortest path metrics, On $k$-ary $n$-cubes: Theory and applications., Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes, The double-bubble problem on the square lattice, An extremal graph problem on a grid and an isoperimetric problem for polyominoes, On Canonical Concurrent Flows, Crossing Number and Graph Expansion, A proof of finite crystallization via stratification, Isoperimetric Problem and Meta-fibonacci Sequences, Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point, Topology and local geometry of the Eden model, Reflect-push methods. Part I: Two dimensional techniques, Bootstrap percolation in random geometric graphs, Maximal fluctuations around the Wulff shape for edge-isoperimetric sets in ${\mathbb{Z}}^d $: a sharp scaling law, Autour de l'inégalité de Brunn-Minkowski, Cleaning a network with brushes, Approximate convexity and an edge-isoperimetric estimate, VERTEX ISOPERIMETRIC PARAMETER OF A COMPUTATION GRAPH, Isoperimetry in integer lattices, A general method to determine limiting optimal shapes for edge-isoperimetric inequalities, Minimising the sum of projections of a finite set, A sharp isoperimetric bound for convex bodies, The carving-width of generalized hypercubes, Connectivity of random k-nearest-neighbour graphs, $H$-coloring tori, Isoperimetric estimates in products, A lower bound on the critical parameter of interlacement percolation in high dimension, SPACES OF SMALL METRIC COTYPE, An impossibility theorem for price-adjustment mechanisms, SPECTRAL GAP FOR SOME INVARIANT LOG‐CONCAVE PROBABILITY MEASURES, On the deterministic complexity of searching local maxima, Bounds on isoperimetric values of trees, Juntas in theℓ₁-grid and Lipschitz maps between discrete tori, On the role of convexity in isoperimetry, spectral gap and concentration, Geometric stability via information theory, Edge integrity of nearest neighbor graphs and separator theorems, Unnamed Item, A new lower bound for the bipartite crossing number with applications, On spanning tree congestion of graphs, Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$, $N^{3/4}$ law in the cubic lattice, THE ISOPERIMETRIC NUMBER OF d–DIMENSIONAL k–ARY ARRAYS, On an equivalence in discrete extremal problems, A discrete variational problem related to Ising droplets at low temperatures.

Cites Work