Isoperimetric stability in lattices

EUROCOMB’23

Abstract
We obtain isoperimetric stability theorems for general Cayley digraphs on $\mathbb{Z}^d$. For any fixed $B$ that generates $\mathbb{Z}^d$ over $\mathbb{Z}$, we characterise the approximate structure of large sets $A$ that are approximately isoperimetric in the Cayley digraph of $B$: we show that $A$ must be close to a set of the form $kZ \cap \mathbb{Z}^d$, where for the vertex boundary $Z$ is the conical hull of $B$, and for the edge boundary $Z$ is the zonotope generated by $B$.

Pages:
107–113
References

B. Barber and J. Erde. Isoperimetry in integer lattices. Discrete Anal., 7, 2018.
https://doi.org/10.19086/da.3555

S. Bezrukov. Isoperimetric problems in discrete spaces. Extremal Problems for Finite Sets, Bolyai Soc. Math. Stud. 3, pages 5991, 1994.

B. Bollobás and I. Leader. Compressions and Isoperimetric Inequalities. J. Comb. Theory Ser. A, 56:4762, 1991.
https://doi.org/10.1016/0097-3165(91)90021-8

B. Bollobás and I. Leader. Edge-isoperimetric inequalities in the grid. Combinatorica, 11:299314, 1991.
https://doi.org/10.1007/BF01275667

A. Dinghas. Über einen geometrischen Satz von Wul für die Gleichgewichtsform von Kristallen. Z. Kristallogr., Mineral. Petrogr., 105, 1944.
https://doi.org/10.1524/zkri.1943.105.1.304

A. Figalli, F. Maggi, and A. Pratelli. A mass transportation approach to quantitative isoperimetric inequalities. Invent. Math., 182(1):167211, 2010.
https://doi.org/10.1007/s00222-010-0261-z

K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresholds versus fractional expectation-thresholds. Ann. of Math., 194(2):475495, 2021.
https://doi.org/10.4007/annals.2021.194.2.2

N. Fusco, F. Maggi, and A. Pratelli. The sharp quantitative isoperimetric inequality. Ann. of Math., 168:941980, 2008.
https://doi.org/10.4007/annals.2008.168.941

B. J. Green. The Polynomial Freiman-Ruzsa Conjecture. Terence Tao's blog, 2007.

J. Kahn and G. Kalai. Thresholds and expectation thresholds. Combin. Probab. Comput., 16:495502, 2007.
https://doi.org/10.1017/S0963548307008474

P. Keevash and E. Long. A stability result for the cube edge isoperimetric inequality. J. Combin. Theory Ser. A, 155:360375, 2018.
https://doi.org/10.1016/j.jcta.2017.11.005

P. Keevash and E. Long. Stability for vertex isoperimetry in the cube. J. Comb. Theory, Ser. B, 145:113144, 2020.
https://doi.org/10.1016/j.jctb.2020.04.009

N. Keller and N. Lifshitz. Approximation of biased Boolean functions of small total influence by DNF's. Bull. Lond. Math. Soc, 50(4):667679, 2018.
https://doi.org/10.1112/blms.12167

I. Leader. Discrete isoperimetric inequalities. Probabilistic Combinatorics and its Applications, 1991.
https://doi.org/10.1090/psapm/044/1141923

M. Ledoux. The concentration of measure phenomenon. Math. Surveys Monogr, 89, 2005.
https://doi.org/10.1090/surv/089

L. Lusternik. Die Brunn-Minkowskische Ungleichung für beliebige messbare Mengen. C. R. Acad. Sci. URSS, 8:5558, 1935.

F. Maggi. Some methods for studying stability in isoperimetric type problems. Bull. Amer. Math. Soc., 45:367408, 2008.
https://doi.org/10.1090/S0273-0979-08-01206-8

F. Maggi. Sets of finite perimeter and geometric variational problems: an introduction to Geometric Measure Theory. Number 135 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2012.
https://doi.org/10.1017/CBO9781139108133

V. Milman and G. Schechtman. Asymptotic Theory of Finite-dimensional Normed Spaces. With an appendix by M. Gromov, volume 1200 of Lecture Notes in Mathematics. Springer, Berlin, 1986.

R. O'Donnell. Analysis of Boolean functions. Cambridge University Press, 2014.

J. Park and H. T. Pham. A proof of the Kahn-Kalai conjecture. arXiv preprint arXiv:2203.17207, 2022.
https://doi.org/10.1109/FOCS54457.2022.00066

H. Plünnecke. Eine zahlentheoretische Anwendung der Graphentheorie. J. Reine Angew. Math, 243:171183, 1970.
https://doi.org/10.1515/crll.1970.243.171

M. Przykucki and A. Roberts. Vertex-isoperimetric stability in the hypercube. J. of Comb. Theory Ser. A, 172, 2020.
https://doi.org/10.1016/j.jcta.2019.105186

J. Radcliffe and E. Veomett. Vertex isoperimetric inequalities for a family of graphs on Zk. Electron. J. Combin., 19(2):P45, 2012.
https://doi.org/10.37236/2426

I. Ruzsa. Sets of sums and commutative graphs. Studia Sci. Math. Hungar, 30:127 148, 1995.

M. Talagrand. Concentration of measure and isoperimetric inequalities in product spaces. Publ. Math. I.H.E.S., 81:73203, 1995.
https://doi.org/10.1007/BF02699376

D. Wang and P. Wang. Discrete isoperimetric problems. SIAM J. Appl. Math., 32:860870, 1977.
https://doi.org/10.1137/0132073

G. Wulff. Zur Frage der Geschwindigkeit des Wachsrurms und der Auösung der Kristallächen. Z. Kristallogr., 34:449530, 1901.
https://doi.org/10.1524/zkri.1901.34.1.449

Metrics

0

Views

0

PDF views