Homomorphism complexes and k-cores

DOI10.1016/J.DISC.2018.06.014MaRDI QIDQ724876zbMATH OpenOpenAlexFDO

Authors Greg Malen

Publication date 26 July 2018

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.07854

zbMATH Keywords

degeneracy\(k\)-coresHom-complexesrandom polyhedral complexes

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30) Relations of low-dimensional topology with graph theory (57M15) Homotopy equivalences in algebraic topology (55P10)

Abstract: We prove that the topological connectivity of a graph homomorphism complex Hom($G,K_m$) is at least $m-D(G)-2$, where $displaystyleD(G)=ma{x}_{HsubseteqG}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, $displaystylechi(G)leqD(G)+1$, as $displaystylechi(G)=minm:extHom(G,K_m)eqvarnothing$. 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$.

Recommendations

• Complexes of graph homomorphisms
• scientific article; zbMATH DE number 2211584
• A short proof of a conjecture on the connectivity of graph coloring complexes
• scientific article; zbMATH DE number 5990556
• Homology of \(\operatorname{Hom}\) complexes

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1380613 (Why is no real title available?)
• scientific article; zbMATH DE number 858007 (Why is no real title available?)
• scientific article; zbMATH DE number 2211584 (Why is no real title available?)
• A short proof of a conjecture on the connectivity of graph coloring complexes
• Between 2- and 3-colorability
• Cohomology of colorings of cycles
• Complexes of graph homomorphisms
• Kneser's conjecture, chromatic number, and homotopy
• Mixing 3-colourings in bipartite graphs
• On colouring random graphs
• Poisson convergence and Poisson processes with applications to random graphs
• Small models of graph colouring manifolds and the Stiefel manifolds \(\Hom(C_{5},K_n)\)
• Sudden emergence of a giant \(k\)-core in a random graph
• The homotopy type of complexes of graph homomorphisms between cycles
• The neighborhood complex of a random graph

Cited in

(5)

• Homology of non-\(k\)-overlapping discs
• Connectedness of certain graph coloring complexes
• Homomorphisms between graphs embedded in surfaces
• Homology of \(\operatorname{Hom}\) complexes
• Homomorphism complexes, reconfiguration, and homotopy for directed graphs

This page was built for publication: Homomorphism complexes and \(k\)-cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724876)