Homomorphisms from the torus

DOI10.1016/J.AIM.2023.109212MaRDI QIDQ6135867zbMATH OpenFDO

Authors Matthew Jenssen, Peter Keevash

Publication date 28 August 2023

Published in Advances in Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph homomorphismcluster expansionpolymer modeldiscrete torusdiscrete spin system

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus $mathbb{Z}_m^n$, where $m$ is even, to any fixed graph: we show that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some dominant phase. This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper $q$-colourings of $mathbb{Z}_m^n$ (so in particular, the discrete hypercube). We give further applications to the study of height functions and (generalised) rank functions on the discrete hypercube and disprove a conjecture of Kahn and Lawrenz. For the proof we combine methods from statistical physics, entropy and graph containers and exploit isoperimetric and algebraic properties of the torus.

Recommendations

• H-coloring tori
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• On weighted graph homomorphisms
• Homomorphisms and polynomial invariants of graphs
• Weighted graph homomorphisms and the Tutte polynomial

Cites work

• scientific article; zbMATH DE number 3833857 (Why is no real title available?)
• scientific article; zbMATH DE number 4160792 (Why is no real title available?)
• scientific article; zbMATH DE number 1023434 (Why is no real title available?)
• scientific article; zbMATH DE number 2151247 (Why is no real title available?)
• A threshold phenomenon for random independent sets in the discrete hypercube
• Algorithmic Pirogov-Sinai theory
• Algorithms for \#BIS-hard problems on expander graphs
• An Ordering on the Even Discrete Torus
• An approximate vertex-isoperimetric inequality for r-sets
• An entropy approach to the hard-core model on bipartite graphs
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Cluster expansion for abstract polymer models
• Counting Independent Sets and Colorings on Random Regular Bipartite Graphs
• Counting independent sets in unbalanced bipartite graphs
• Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures
• Fast algorithms for general spin systems on bipartite expanders
• Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
• Generalized rank functions and an entropy argument
• Grounded Lipschitz functions on trees are typically flat
• High-dimensional Lipschitz functions are typically flat
• Independent sets in the hypercube revisited
• Independent sets in the middle two layers of Boolean lattice
• Left and right convergence of graphs with bounded degree
• Lipschitz functions on expanders are typically flat
• Long-range order in the 3-state antiferromagnetic Potts model in high dimensions
• Matroidal bijections between graphs
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• On Counting Independent Sets in Sparse Graphs
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• On a Method of Calculation of Semi-Invariants
• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• On random graph homomorphisms into \({\mathbb{Z}}\)
• On weighted graph homomorphisms
• Optimal numberings and isoperimetric problems on graphs
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• Range of cube-indexed random walk
• Rigidity of 3-colorings of the discrete torus
• Sampling 3-colourings of regular bipartite graphs
• Sampling independent sets in the discrete torus
• Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Torpid mixing of local Markov chains on 3-colorings of the discrete torus
• H-coloring tori
• \(H\)-colouring bipartite graphs

Cited in

(7)

• On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
• H-coloring tori
• Independent sets in the hypercube revisited
• On the zeroes of hypergraph independence polynomials
• Torus HOMFLYPT as the Hall-Littlewood polynomials
• Characterization of homogeneous torus manifolds
• Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)

This page was built for publication: Homomorphisms from the torus

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