Signed and weighted graphs (05C22) Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)
Abstract: We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus , where 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 -colourings of (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
Cites work
- H-coloring tori
- \(H\)-colouring bipartite graphs
- A threshold phenomenon for random independent sets in the discrete hypercube
- Algorithmic Pirogov-Sinai theory
- Algorithms for \#BIS-hard problems on expander graphs
- An approximate vertex-isoperimetric inequality for r-sets
- An entropy approach to the hard-core model on bipartite graphs
- An Ordering on the Even Discrete Torus
- 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
- 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?)
- 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 a Method of Calculation of Semi-Invariants
- On Counting Independent Sets in Sparse Graphs
- On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
- On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
- 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
Cited in
(14)- On homomorphisms from the Hamming cube to \(\mathbb{Z}\)
- Delocalization of uniform graph homomorphisms from \({\mathbb{Z}}^2\) to \({\mathbb{Z}} \)
- Torus HOMFLYPT as the Hall-Littlewood polynomials
- Independent sets in the hypercube revisited
- On the zeroes of hypergraph independence polynomials
- Lipschitz functions on weak expanders
- Counting independent sets in percolated graphs via the Ising model
- On the evolution of structure in triangle-free graphs
- Independent sets in discrete tori of odd sidelength
- The number of colorings of the middle layers of the Hamming cube
- A sharp threshold for a random version of Sperner's theorem
- H-coloring tori
- Title not available (Why is no real title available?)
- Characterization of homogeneous torus manifolds
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)
