×

Hardness of almost embedding simplicial complexes in \(\mathbb {R}^d\). (English) Zbl 1415.57016

The authors introduce notion of “almost embedding” of a finite \(k\)-dimensional simplicial complex \(K\) in \(\mathbb{R}^d\) and discuss related algorithmic problems. In case of embeddings of \(|K| \to \mathbb{R}^d\) this problem has been treated in [J. Matoušek et al., J. Eur. Math. Soc. (JEMS) 13, No. 2, 259–295 (2011; Zbl 1208.68130)]. If \(\tilde{K}\) denotes the simplicial deleted product of \(K\) and \(f:|K| \to \mathbb{R}^d\) an almost embedding, then we have an equivariant map \(\tilde{f}: \tilde{K} \to S^{d-1}\). The main result of the paper says that under some assumptions we may have \(K\) and an equivariant map \(\tilde{K} \to S^{d-1}\) but not an almost embedding of \(|K|\). These assumptions are the following: P \(\neq\) NP, \(d, k \geq 2\) and \(d=3k/2 + 1\). From the algorithmic point of view the problem of recognition of almost embeddability is NP-hard.

MSC:

57Q35 Embeddings and immersions in PL-topology
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05E45 Combinatorial aspects of simplicial complexes

Citations:

Zbl 1208.68130
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Avvakumov, S., Mabillard, I., Skopenkov, A., Wagner, U.: Eliminating higher-multiplicity intersections, III. Codimension 2. arXiv:1511.03501 · Zbl 1504.57042
[2] Bárány, I., Blagojević, P.V.M., Ziegler, G.M.: Tverberg’s theorem at 50: extensions and counterexamples. Notices Am. Math. Soc. 63(7), 732-739 (2016). http://www.ams.org/journals/notices/201607 · Zbl 1358.52022
[3] Blagojevič, P.V.M., Ziegler, G.M.: Beyond the Borsuk-Ulam theorem: the topological Tverberg story. In: Loebl, M., Nešetřil, J., Thomas, R. (eds.) A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pp. 273-341. Springer, Cham (2017). arXiv:1605.07321 · Zbl 1470.52007
[4] Boltyanskiy, V.G., Efremovich, V.A.: Intuitive Combinatorial Topology. Universitext. Springer, New York (2001) · doi:10.1007/978-1-4757-5604-3
[5] Čadek, M., Krčal, M., Vokřinek, L.: Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom. 57(4), 915-965 (2017) · Zbl 1373.55018 · doi:10.1007/s00454-016-9855-6
[6] Cohen, M.M.: Simplicial structures and transverse cellularity. Ann. Math. 85, 218-245 (1967) · Zbl 0147.42602 · doi:10.2307/1970440
[7] Flores, A.: Über \[n\] n-dimensionale Komplexe die im \[R_{2n + 1}\] R2n+1 absolut selbstverschlungen sind. Ergeb. Math. Kolloq. 4, 6-7 (1932/1934)
[8] Freedman, M., Krushkal, V.: Geometric complexity of embeddings in \[{\mathbb{R}}^d\] Rd. Geom. Funct. Anal. 24(5), 1406-1430 (2014). arXiv:1311.2667 · Zbl 1366.57013 · doi:10.1007/s00039-014-0272-9
[9] Freedman, M.H., Krushkal, V.S., Teichner, P.: Van Kampen’s embedding obstruction is incomplete for 2-complexes in \[{\mathbb{R}}^4\] R4. Math. Res. Lett. 1(2), 167-176 (1994) · Zbl 0847.57005 · doi:10.4310/MRL.1994.v1.n2.a4
[10] Goaoc, X., Paták, P., Patáková, Z., Tancer, M., Wagner, U.: Bounding Helly numbers via Betti numbers. In: Loebl, M., Nešetřil, J., Thomas, R. (eds.) A Journey Through Discrete Mathematics: A Tribute to Jiří Matoušek, pp. 407-447. Springer, Cham (2017). arXiv:1310.4613 · Zbl 1390.52012
[11] Gonçalves, D., Skopenkov, A.: Embeddings of homology equivalent manifolds with boundary. Topol. Appl. 153(12), 2026-2034 (2006). arXiv:1207.1326 · Zbl 1105.57022 · doi:10.1016/j.topol.2005.07.009
[12] Hudson, J.F.P.: Piecewise Linear Topology. University of Chicago Lecture Notes. Benjamin, New York (1969) · Zbl 0189.54507
[13] Matoušek, J.: A Helly-type theorem for unions of convex sets. Discrete Comput. Geom. 18(1), 1-12 (1997) · Zbl 0889.52009 · doi:10.1007/PL00009305
[14] Matoušek, J., Tancer, M., Wagner, U.: Hardness of embedding simplicial complexes in \[{\mathbb{R}}^d\] Rd. J. Eur. Math. Soc. 13(2), 259-295 (2011). arXiv:0807.0336 · Zbl 1208.68130 · doi:10.4171/JEMS/252
[15] Segal, J., Spież, S.: Quasi embeddings and embeddings of polyhedra in \[{\mathbb{R}}^m\] Rm. Topol. Appl. 45(3), 275-282 (1992) · Zbl 0768.57012 · doi:10.1016/0166-8641(92)90009-O
[16] Segal, J., Skopenkov, A., Spież, S.: Embeddings of polyhedra in \[{\mathbb{R}}^m\] Rm and the deleted product obstruction. Topol. Appl. 85(1-3), 335-344 (1998) · Zbl 0934.57025 · doi:10.1016/S0166-8641(97)00157-0
[17] Shapiro, A.: Obstructions to the imbedding of a complex in a euclidean space I. The first obstruction. Ann. Math. 66, 256-269 (1957) · Zbl 0085.37701 · doi:10.2307/1969998
[18] Seifert, H., Threlfall, W.: Seifert and Threlfall: A Textbook of Topology. Pure and Applied Mathematics, vol. 89. Academic Press, New York (1980) · Zbl 0469.55001
[19] Skopenkov, A.B.: Embedding and knotting of manifolds in Euclidean spaces. In: Young, N., Choi, Y. (eds.) Surveys in Contemporary Mathematics. London Mathematical Society Lecture Note Series, vol. 347, pp. 248-342. Cambridge University Press, Cambridge (2008). arXiv:math/0604045 · Zbl 1154.57019
[20] Skopenkov, A.: Realizability of hypergraphs and Ramsey link theory. arXiv:1402.0658
[21] Skopenkov, A.: A user’s guide to disproof of topological Tverberg conjecture. arXiv:1605.05141 · Zbl 1406.52015
[22] Skopenkov, A.: On van Kampen-Flores, Conway-Gordon-Sachs and Radon theorems. Russ. Math. Surveys 73(2), 344-377 (2018). arXiv:1704.00300
[23] Skopenkov, A.: Algebraic topology from algorithmic point of view (draft of a book). http://www.mccme.ru/circles/oim/algor.pdf
[24] Skopenkov, A.: Invariants of graph drawings in the plane. arXiv:1805.10237 · Zbl 1039.57015
[25] van Kampen, E.R.: Komplexe in euklidischen Räumen. Abh. Math. Sem. Univ. Hamburg 9(1), 72-78 (1932) · JFM 58.0615.02 · doi:10.1007/BF02940628
[26] Volodin, I.A., Kuznetsov, V.E., Fomenko, A.T.: The problem of discriminating algorithmically the standard three-dimensional sphere. Russ. Math. Surveys 29(5), 71-172 (1974) · Zbl 0311.57001 · doi:10.1070/RM1974v029n05ABEH001296
[27] Weber, C.: Plongements de polyhèdres dans le domaine métastable. Comment. Math. Helv. 42, 1-27 (1967) · Zbl 0152.22402 · doi:10.1007/BF02564408
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.