Warmth and edge spaces of graphs

Research output: Contribution to journalArticleScientificpeer-review

Researchers

Research units

  • Texas State University

Abstract

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(K2,G), a space of homomorphisms from a edge K2 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(K2,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(K2,G). We succeed in establishing a first nontrivial case of the conjecture, by showing that ζ(G)≤3 if Hom(K2,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 Ka,b for a+b=n. This provides an analogue for a similar result in the context of Hom complexes.

Details

Original languageEnglish
Pages (from-to)176-194
Number of pages19
JournalAdvances in Applied Mathematics
Volume96
Publication statusPublished - 1 May 2018
MoE publication typeA1 Journal article-refereed

    Research areas

  • Chromatic number, Combinatorial statistical mechanics, Connectivity, Graph homomorphism, Neighborhood complex, Topological methods, Warmth

ID: 18015037