Homomorphisms from the torus

Matthew Jenssen, Peter Keevash

Research output: Working paper/PreprintPreprint

35 Downloads (Pure)

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.
Original languageEnglish
Publication statusPublished - 17 Sep 2020

Keywords

  • math.CO
  • math.PR

Fingerprint

Dive into the research topics of 'Homomorphisms from the torus'. Together they form a unique fingerprint.

Cite this