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 , let
be the graph parameter introduced by Colin de Verdière. In this paper we show that
if and only if
is linklessly embeddable (in
). 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
-spheres in certain mappings
. This result might be of interest in its own right. We also derive that
for each linklessly embeddable graph
, where
is the graph parameter introduced by van der Holst, Laurent, and Schrijver. (It is the largest dimension of any subspace
of
such that for each nonzero
, the positive support of
induces a nonempty connected subgraph of
.)
- [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.
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