Homomorphism Complexes and k-Cores

2016/01/28 by Greg Malen, Malen, Greg
Mathematics · #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics #math.AT #math.CO

paper · pdf · doi:10.48550/arxiv.1601.07854

arxiv created 2016/02/13 · arxiv updated 2016/02/16

Abstract

We prove that the topological connectivity of a graph homomorphism complex Hom(G,K_m) is at least m-D(G)-2, where D(G)=max_{H⊆ G}δ(H). This is a strong generalization of a theorem of Cukić and Kozlov, in which D(G) is replaced by the maximum degree Δ(G). It also generalizes the graph theoretic bound for chromatic number, χ(G)≤ D(G)+1, as χ(G)=min\ m:Hom(G,K_m)≠\varnothing\. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom(G(n,p),K_m) when p=c/n for a fixed constant c > 0.

Related

• A short proof of a conjecture on the higher connectivity of graph coloring complexes
• Higher connectivity of graph coloring complexes
• Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles
• Topology of Hom complexes and test graphs for bounding chromatic number
• Simple S_r-homotopy types of Hom complexes and box complexes associated to r-graphs