Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-11T15:34:24.906Z Has data issue: false hasContentIssue false
  • English
  • Français

The Growth Constant of Odd Cutsets in High Dimensions

Part of: Equilibrium statistical mechanics Graph theory Special processes

Published online by Cambridge University Press:  14 August 2017

OHAD NOY FELDHEIM  and
YINON SPINKA
OHAD NOY FELDHEIM
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305, USA (e-mail: ohadf@netvision.net.il)
YINON SPINKA
Affiliation:
School of Mathematical Sciences, Tel Aviv University, Tel Aviv, 69978, Israel (e-mail: yinonspi@post.tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A cutset is a non-empty finite subset of ℤd which is both connected and co-connected. A cutset is odd if its vertex boundary lies in the odd bipartition class of ℤd. Peled [18] suggested that the number of odd cutsets which contain the origin and have n boundary edges may be of order eΘ(n/d) as d → ∞, much smaller than the number of general cutsets, which was shown by Lebowitz and Mazel [15] to be of order dΘ(n/d). In this paper, we verify this by showing that the number of such odd cutsets is (2+o(1))n/2d.

MSC classification

Primary: 05C10: Planar graphs; geometric and topological aspects of graph theory
Secondary: 05C30: Enumeration in graph theory 82B41: Random walks, random surfaces, lattice animals, etc. 60K35: Interacting random processes; statistical mechanics type models; percolation theory 82B20: Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 2 , March 2018 , pp. 208 - 227
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Balister, P. and Bollobás, B. (2007) Counting regions with bounded surface area. Commun. Math. Phys. 273 305–315.Google Scholar
[2] Bollobás, B. (2006) The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press.CrossRefGoogle Scholar
[3] Feldheim, O. N. and Peled, R. Rigidity of 3-colorings of the discrete torus. Ann. Inst. H. Poincaré (B), to appear.Google Scholar
[4] Feldheim, O. N. and Spinka, Y. Long-range order in the 3-state antiferromagnetic Potts model in high dimensions. J. Eur. Math. Soc. (JEMS), to appear.Google Scholar
[5] Galvin, D. (2003) On homomorphisms from the Hamming cube to Z . Israel J. Math. 138 189–213.CrossRefGoogle Scholar
[6] Galvin, D. (2007) Sampling 3-colourings of regular bipartite graphs. Electron. J. Probab. 12 481–497.Google Scholar
[7] Galvin, D. (2008) Sampling independent sets in the discrete torus. Random Struct. Alg. 33 356–376.Google Scholar
[8] Galvin, D. and Kahn, J. (2004) On phase transition in the hard-core model on ℤ d . Combin. Probab. Comput. 13 137–164.Google Scholar
[9] Galvin, D. and Randall, D. (2007) Torpid mixing of local Markov chains on 3-colorings of the discrete torus. In SODA 2007: Proc. 18th Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 376–384.Google Scholar
[10] Galvin, D. and Tetali, P. (2004) Slow mixing of Glauber dynamics for the hard-core model on the hypercube. In SODA 2004: Proc. 15th Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 466–467.Google Scholar
[11] Galvin, D. and Tetali, P. (2006) Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Struct. Alg. 28 427–443.CrossRefGoogle Scholar
[12] Galvin, D., Kahn, J., Randall, D. and Sorkin, G. (2015) Phase coexistence and torpid mixing in the 3-coloring model on ℤ d . SIAM J. Discrete Math. 29 1223–1244.Google Scholar
[13] Korshunov, A. D. (1981) On the number of monotone Boolean functions. Problemy Kibernet. 38 5–108.Google Scholar
[14] Korshunov, A. D. and Sapozhenko, A. A. (1983) The number of binary codes with distance 2 (in Russian). Problemy Kibernet. 40 111–130.Google Scholar
[15] Lebowitz, J. L. and Mazel, A. E. (1998) Improved Peierls argument for high-dimensional Ising models. J. Statist. Phys. 90 1051–1059.Google Scholar
[16] Lovász, L. (1975) On the ratio of optimal integral and fractional covers. Discrete Math. 13 383–390.Google Scholar
[17] Miranda, Y. M. and Slade, G. (2011) The growth constants of lattice trees and lattice animals in high dimensions. Electron. Comm. Probab. 16 129–136.Google Scholar
[18] Peled, R. (2017) High-dimensional Lipschitz functions are typically flat. Ann. Probab. 45 1351–1447.Google Scholar
[19] Peled, R. and Samotij, W. (2014) Odd cutsets and the hard-core model on ℤ d . Ann. Inst. Henri Poincaré B 50 975–998.CrossRefGoogle Scholar
[20] Sapozhenko, A. A. (1987) On the number of connected subsets with given cardinality of the boundary in bipartite graphs (in Russian). Metody Diskretnogo Analiza. 45 42–70.Google Scholar
[21] Sapozhenko, A. A. (1989) The number of antichains in ranked partially ordered sets. Diskretnaya Matematika 1 74–93.Google Scholar
[22] Sapozhenko, A. A. (1991) On the number of antichains in multilevelled ranked posets. Discrete Math. Appl. 1 149–170.Google Scholar
[23] Timár, Á. (2013) Boundary-connectivity via graph theory. Proc. Amer. Math. Soc. 141 475–480.Google Scholar