A simple proof for folds on both sides in complexes of graph homomorphisms

By Dmitry N. Kozlov. 2004

55 citations recorded by the source corpus.

In this paper we study implications of folds in both parameters of Lovasz' Hom(-,-) complexes. There is an important connection between the topological properties of these complexes and lower bounds for chromatic numbers. We give a very short and conceptual proof of the fact that if G - v is a fold of G, then bdHom(G, H) collapses onto bdHom(G - v, H), whereas Hom(H, G) collapses onto Hom(H, G - v). We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if φ is a closure operator on P, then A(P) collapses onto Δ(φ(P)).

Subfields: Computational Theory and Mathematics, Geometry and Topology, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/6137bb5bf22c96e2f72d5ef28de9b59a717581d5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Mathematical Physics

Citations in the corpus

Proof of the Lovász conjecture (2004, result): “2) ≥2. This is true for all parameters n≥5, k≥2, except for k= 2. 4.2. The cell complex of homomorphismsfrom a tree to a complete graph. In the next proposition we summarize several results proved in [2, 11]. Proposition 4.6. [2, Propositions 4.3, 5.4, and 5.5], [11]. Let T be a tree with at least o”
Chromatic numbers, morphism complexes, and Stiefel-Whitney characteristic classes (2005, methodology): “Here, we survey the study of the Hom-complexes, and the ways these can be used to obtain lower bounds for the chromatic numbers of graphs, presented in a recent series of papers [BK03a, BK03b, BK04, CK04a, CK04b, Ko04 , Ko05b].”