Simple homotopy types of Hom-complexes, neighborhood complexes, Lovász complexes, and atom crosscut complexes

Abstract

In this paper we provide concrete combinatorial formal deformation algorithms, namely sequences of elementary collapses and expansions, which relate various previously extensively studied families of combinatorially defined polyhedral complexes. To start with, we give a sequence of elementary collapses leading from the barycentric subdivision of the neighborhood complex to the Lovász complex of a graph. Then, for an arbitrary lattice $\mathcal{L}$ we describe a formal deformation of the barycentric subdivision of the atom crosscut complex $\Gamma (\mathcal{L})$ to its order complex $\Delta (\bar{\mathcal{L}})$. We proceed by proving that the complex of sets bounded from below $\mathcal{J}(\mathcal{L})$ can also be collapsed to $\Delta (\bar{\mathcal{L}})$. Finally, as a pinnacle of our project, we apply all these results to certain graph complexes. Namely, by describing an explicit formal deformation, we prove that, for any graph $G$, the neighborhood complex $\mathcal{N}(G)$ and the polyhedral complex $\text{Hom}(K_2,G)$ have the same simple homotopy type in the sense of Whitehead.

The revised version to appear in Topology Appl

References in corpus (3)

• Collapsing along monotone poset maps
• Complexes of graph homomorphisms
• The homotopy type of complexes of graph homomorphisms between cycles

Cited by in corpus (9)

• Homotopy groups of Hom complexes of graphs
• Homology tests for graph colorings
• Hom complexes and homotopy theory in the category of graphs
• Simplicial simple-homotopy of flag complexes in terms of graphs
• On the neighborhood complex of $\vec{s}$-stable Kneser graphs
• A Unified Topological Approach to Data Science
• Lovász' original lower bound: Getting tighter bounds and Reducing computational complexity
• Linear colorings of simplicial complexes and collapsing
• The crosscut poset and the fixed point property