Remote Access Proceedings of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9939-98-04244-0
MathSciNet review: 1443840
Full-text PDF

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?)

  • [1] R. Bacher, Y. Colin de Verdière, Multiplicités des valeurs propres et transformations étoile-triangle des graphes, Bulletin de la Société Mathématique de France 123 (1995) 101-117. MR 96k:05129
  • [2] E.G. Bajmóczy, I. Bárány, On a common generalization of Borsuk's and Radon's theorem, Acta Mathematica Academiae Scientiarum Hungaricae 34 (1979) 347-350. MR 84g:52007
  • [3] T. Böhme, On spatial representations of graphs, in: Contemporary Methods in Graph Theory (R. Bodendieck, ed.), BI-Wiss.-Verl. Mannheim, Wien/Zurich, 1990, pp. 151-167. MR 93a:05053
  • [4] Y. Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, Journal of Combinatorial Theory, Series B 50 (1990) 11-21. MR 91m:05068
  • [5] Y. Colin de Verdière, On a new graph invariant and a criterion for planarity, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), vol. 147, Contemporary Mathematics, American Mathematical Society, Providence, Rhode Island, 1993, pp. 137-147. MR 94h:05023
  • [6] H. van der Holst, A short proof of the planarity characterization of Colin de Verdière, Journal of Combinatorial Theory, Series B 65 (1995) 269-272. MR 96g:05050
  • [7] H. van der Holst, M. Laurent, A. Schrijver, On a minor-monotone graph invariant, Journal of Combinatorial Theory, Series B 65 (1995) 291-304. MR 96k:05096
  • [8] H. van der Holst, L. Lovász, A. Schrijver, On the invariance of Colin de Verdière's graph parameter under clique sums, Linear Algebra and Its Applications 226 (1995) 509-517. MR 97e:05113
  • [9] N. Robertson, P.D. Seymour, R. Thomas, A survey of linkless embeddings, in: Graph Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics, vol. 147, American Mathematical Society, Providence, Rhode Island, 1993, pp. 125-136. MR 94g:05026
  • [10] N. Robertson, P. Seymour, R. Thomas, Sachs' linkless embedding conjecture, Journal of Combinatorial Theory, Series B 64 (1995) 185-227. MR 96m:05072
  • [11] H. Saran, Constructive Results in Graph Minors: Linkless Embeddings, Ph.D. Thesis, University of California at Berkeley, 1989.
  • [12] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937) 570-590.

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: https://doi.org/10.1090/S0002-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

American Mathematical Society