Warmth and edge spaces of graphs

In this paper we study a pair of numerical parameters associated to a graph G. On the one hand, we consider the (topological) connectivity of the polyhedral complex Hom(K₂,G), a space of homomorphisms from a edge K₂ into G. This approach dates back to the neighborhood complexes introduced by Lovász in his proof of the Kneser conjecture. In another direction we study the warmth ζ(G) of a graph G, a parameter introduced by Brightwell and Winkler based on the asymptotic behavior of d-branching walks in G and inspired by constructions in statistical physics. Both the warmth of G and the connectivity of Hom(K₂,G) provide lower bounds on the chromatic number of G. Here we seek to relate these two constructions, and in particular we provide evidence for the conjecture that the warmth of a graph G is always less than three plus the connectivity of Hom(K₂,G). We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ(G)≤3 if Hom(K₂,G) has an infinite first homology group. We also calculate warmth for a family of ‘twisted toroidal’ graphs that are important extremal examples in the context of Hom complexes. Finally we show that ζ(G)≤n−1 if a graph G does not have the complete bipartite graph K_a,b for a+b=n. This provides an analogue for a similar result in the context of Hom complexes.