Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8902895 | Discrete Mathematics | 2018 | 8 Pages |
Abstract
For any fixed graph G, we prove that the topological connectivity of the graph homomorphism complex Hom(G,Km) is at least mâD(G)â2, where D(G)=maxHâGδ(H), for δ(H) the minimum degree of a vertex in a subgraph H. This generalizes a theorem of CÌukiÄ and Kozlov, in which the maximum degree Î(G) was used in place of D(G), and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, Ï(G)â¤D(G)+1, as Ï(G)=min{m:Hom(G,Km)â â
}. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom(G(n,p),Km) when p=cân for a fixed constant c>0.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Greg Malen,