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

Abstract

In this paper we study implications of folds in both parameters of Lovász’ <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace upper H monospace o monospace m left-parenthesis minus comma minus right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">H</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">m</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mo> − </mml:mo> <mml:mo>,</mml:mo> <mml:mo> − </mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathtt {Hom}(-,-)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G minus v"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo> − </mml:mo> <mml:mi>v</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">G-v</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a fold of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="b d monospace upper H monospace o monospace m left-parenthesis upper G comma upper H right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>bd</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">H</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">m</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>H</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {bd}\mathtt {Hom}(G,H)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> collapses onto <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="b d monospace upper H monospace o monospace m left-parenthesis upper G minus v comma upper H right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>bd</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">H</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">m</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo> − </mml:mo> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>H</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\operatorname {bd}\mathtt {Hom}(G-v,H)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , whereas <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace upper H monospace o monospace m left-parenthesis upper H comma upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">H</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">m</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>,</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathtt {Hom}(H,G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> collapses onto <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace upper H monospace o monospace m left-parenthesis upper H comma upper G minus v right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">H</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">m</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>,</mml:mo> <mml:mi>G</mml:mi> <mml:mo> − </mml:mo> <mml:mi>v</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathtt {Hom}(H,G-v)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We also give an easy inductive proof of the only nonelementary fact which we use for our arguments: if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="phi"> <mml:semantics> <mml:mi> φ </mml:mi> <mml:annotation encoding="application/x-tex">\varphi</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a closure operator on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P"> <mml:semantics> <mml:mi>P</mml:mi> <mml:annotation encoding="application/x-tex">P</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Delta left-parenthesis upper P right-parenthesis"> <mml:semantics> <mml