Can I read Homomorphism Complexes and k-Cores on EtoBox?

Homomorphism Complexes and k-Cores by Malen, Greg is a scholarly article available to read on EtoBox.

What is Homomorphism Complexes and k-Cores about?

We prove that the topological connectivity of a graph homomorphism complex Hom($G,K_m$) is at least $m-D(G)-2$, where $\displaystyle D(G)=\max_{H\subseteq G}\delta(H)$. This is a strong generalization of a theorem of Cuki\'{c} and Kozlov, in which $D(G)$ is replaced by the maximum degree $\Delta(G)$. It also generalizes the graph theoretic bound for chromatic number, $\displaystyle\chi(G)\leq D(G)+1$, as $\displaystyle\chi(G)=\min\{ m:\text{Hom}(G,K_m)\neq\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$.

Author

Malen, Greg

Published

2016

Language

EN