Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

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


Authors: László Lovász and Alexander Schrijver
Journal: Proc. Amer. Math. Soc. 126 (1998), 1275-1285
MSC (1991): Primary 05C10, 05C50, 57M15; Secondary 05C50, 57N15
MathSciNet review: 1443840
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: For any undirected graph $G$, let $\mu(G)$ be the graph parameter introduced by Colin de Verdière. In this paper we show that $\mu(G)\leq 4$ if and only if $G$ is linklessly embeddable (in $\mathcal{R}^3$). 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 $(k-1)$-spheres in certain mappings $\phi:S^{2k}\to \mathcal{R}^{2k-1}$. This result might be of interest in its own right. We also derive that $\lambda(G)\leq 4$ for each linklessly embeddable graph $G=(V,E)$, where $\lambda(G)$ is the graph parameter introduced by van der Holst, Laurent, and Schrijver. (It is the largest dimension of any subspace $L$ of $\mathcal{R}^V$ such that for each nonzero $x\in L$, the positive support of $x$ induces a nonempty connected subgraph of $G$.)


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05C10, 05C50, 57M15, 05C50, 57N15

Retrieve articles in all journals with MSC (1991): 05C10, 05C50, 57M15, 05C50, 57N15


Additional Information

László Lovász
Affiliation: Department of Computer Science, Yale University, New Haven, Connecticut 06520
Email: lovasz@cs.yale.edu

Alexander Schrijver
Affiliation: CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands and Department of Mathematics, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, The Netherlands
Email: lex@cwi.nl

DOI: http://dx.doi.org/10.1090/S0002-9939-98-04244-0
PII: S 0002-9939(98)04244-0
Received by editor(s): October 15, 1996
Additional Notes: Research partially done while visiting the Department of Computer Science at Yale University.
Communicated by: Jeffry N. Kahn
Article copyright: © Copyright 1998 American Mathematical Society