Math @ Duke

Publications [#335543] of Greg Malen
Papers Published
 Malen, G, Homomorphism complexes and kcores,
Discrete Mathematics, vol. 341 no. 9
(September, 2018),
pp. 25672574, 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 highdimensional 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

