Publications [#335543] of Greg Malen

Papers Published

1. Malen, G, Homomorphism complexes and k-cores, Discrete Mathematics, vol. 341 no. 9 (September, 2018), pp. 2567-2574, Elsevier BV [doi]
   (last updated on 2020/07/05)

   Abstract:
   © 2018 Elsevier B.V. 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.