Homomorphisms from the torus

22 October 2019
Matthew Jenssen

Further Information: 

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Z_m^n, where m is even, to any fixed graph. Our main result establishes the "phase coexistence" phenomenon in a strong form: it shows 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 Z_m^n (so in particular, the discrete hypercube). For the proof we develop a `Cluster Expansion Method', which we expect to have further applications, by combining machinery from statistical physics, entropy and graph containers. This is joint work with Peter Keevash.

  • Combinatorial Theory Seminar