Homomorphisms from the torus

DOI10.1016/J.AIM.2023.109212zbMATH Open1520.05066arXiv2009.08315MaRDI QIDQ6135867FDOQ6135867

Peter Keevash, Matthew Jenssen

Publication date: 28 August 2023

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• 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
• On homomorphisms from the Hamming cube 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)