×

A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs. (English) Zbl 0886.05055

Summary: 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\)).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
57N15 Topology of the Euclidean \(n\)-space, \(n\)-manifolds (\(4 \leq n \leq \infty\)) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Roland Bacher and Yves Colin de Verdière, Multiplicités des valeurs propres et transformations étoile-triangle des graphes, Bull. Soc. Math. France 123 (1995), no. 4, 517 – 533 (French, with English and French summaries). · Zbl 0845.05068
[2] I. Bárány and L. Lovász, Borsuk’s theorem and the number of facets of centrally symmetric polytopes, Acta Math. Acad. Sci. Hungar. 40 (1982), no. 3-4, 323 – 329. · Zbl 0514.52003 · doi:10.1007/BF01903592
[3] Thomas Böhme, On spatial representations of graphs, Contemporary methods in graph theory, Bibliographisches Inst., Mannheim, 1990, pp. 151 – 167. · Zbl 0718.05054
[4] Yves Colin de Verdière, Sur un nouvel invariant des graphes et un critère de planarité, J. Combin. Theory Ser. B 50 (1990), no. 1, 11 – 21 (French). · Zbl 0742.05061 · doi:10.1016/0095-8956(90)90093-F
[5] Yves Colin de Verdière, On a new graph invariant and a criterion for planarity, Graph structure theory (Seattle, WA, 1991) Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, 1993, pp. 137 – 147. · Zbl 0791.05024 · doi:10.1090/conm/147/01168
[6] Hein van der Holst, A short proof of the planarity characterization of Colin de Verdière, J. Combin. Theory Ser. B 65 (1995), no. 2, 269 – 272. · Zbl 0841.05025 · doi:10.1006/jctb.1995.1054
[7] Hein van der Holst, Monique Laurent, and Alexander Schrijver, On a minor-monotone graph invariant, J. Combin. Theory Ser. B 65 (1995), no. 2, 291 – 304. · Zbl 0839.05034 · doi:10.1006/jctb.1995.1056
[8] Hein van der Holst, László Lovász, and Alexander Schrijver, On the invariance of Colin de Verdière’s graph parameter under clique sums, Linear Algebra Appl. 226/228 (1995), 509 – 517. · Zbl 0834.05036 · doi:10.1016/0024-3795(95)00160-S
[9] Neil Robertson, P. D. Seymour, and Robin Thomas, Structural descriptions of lower ideals of trees, Graph structure theory (Seattle, WA, 1991) Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, 1993, pp. 525 – 538. · Zbl 0799.05015 · doi:10.1090/conm/147/01198
[10] Neil Robertson, Paul Seymour, and Robin Thomas, Sachs’ linkless embedding conjecture, J. Combin. Theory Ser. B 64 (1995), no. 2, 185 – 227. · Zbl 0832.05032 · doi:10.1006/jctb.1995.1032
[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. · JFM 63.0550.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.