A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs

László Lovász, Alexander Schrijver

Proceedings of the American Mathematical Society · 1998 · 78 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

For any undirected graph <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> , let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> μ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mu (G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the graph parameter introduced by Colin de Verdière. In this paper we show that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu left-parenthesis upper G right-parenthesis less-than-or-equal-to 4"> <mml:semantics> <mml:mrow> <mml:mi> μ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:mn>4</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\mu (G)\leq 4</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if and only if <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> is linklessly embeddable (in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper R cubed"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mn>3</mml:mn> </mml:msup> <mml:annotation encoding="application/x-tex">\mathbb {R}^3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ). This forms a spectral characterization of linklessly embeddable graphs, and was conjectured by Robertson, Seymour, and Thomas. A key ingredient is a Borsuk-type theorem on the existence of a pair of antipodal linked <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis k minus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(k-1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -spheres in certain mappings <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="phi colon upper S Superscript 2 k Baseline right-arrow double-struck upper R Superscript 2 k minus 1"> <mml:semantics> <mml:mrow> <mml:mi> ϕ </mml:mi> <mml:mo>:</mml:mo> <mml:msup> <mml:mi>S</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> <mml:mo stretchy="false"> → </mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">\phi :S^{2k}\to \mathbb {R}^{2k-1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . This result might be of interest in its own right. We also derive that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis upper G right-parenthesis less-than-or-equal-to 4"> <mml:semantics> <mml:mrow> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:mn>4</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda (G)\leq 4</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for each linklessly embeddable graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G equals left-parenthesis upper V comma upper E right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>E</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G=(V,E)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> λ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\lambda (G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the graph parameter introduced by van der Holst, Laurent, and

References

7