{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:37Z","timestamp":1740109597650,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T00:00:00Z","timestamp":1689811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"austrian science fund","doi-asserted-by":"publisher","award":["P31312-N35"],"award-info":[{"award-number":["P31312-N35"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001824","name":"grantov\u00e1 agentura \u010desk\u00e9 republiky","doi-asserted-by":"publisher","award":["project P201\/12\/G028"],"award-info":[{"award-number":["project P201\/12\/G028"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,10]]},"abstract":"Abstract<\/jats:title>We present an algorithm that, given finite diagrams of simplicial sets X<\/jats:italic>,\u00a0A<\/jats:italic>,\u00a0Y<\/jats:italic>, i.e., functors $${\\mathcal {I}}^\\textrm{op}\\rightarrow {\\textsf {s}} {\\textsf {Set}}$$<\/jats:tex-math>\n \n \n \n I<\/mml:mi>\n <\/mml:mrow>\n op<\/mml:mtext>\n <\/mml:msup>\n \u2192<\/mml:mo>\n s<\/mml:mi>\n Set<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such that (X<\/jats:italic>,\u00a0A<\/jats:italic>) is a cellular pair, $$\\dim X\\le 2\\cdot {\\text {conn}}Y$$<\/jats:tex-math>\n \n dim<\/mml:mo>\n X<\/mml:mi>\n \u2264<\/mml:mo>\n 2<\/mml:mn>\n \u00b7<\/mml:mo>\n conn<\/mml:mtext>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, $${\\text {conn}}Y\\ge 1$$<\/jats:tex-math>\n \n conn<\/mml:mtext>\n Y<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, computes the set $$[X,Y]^A$$<\/jats:tex-math>\n \n \n [<\/mml:mo>\n X<\/mml:mi>\n ,<\/mml:mo>\n Y<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n A<\/mml:mi>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of homotopy classes of maps of diagrams $$\\ell :X\\rightarrow Y$$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n :<\/mml:mo>\n X<\/mml:mi>\n \u2192<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> extending a given $$f:A\\rightarrow Y$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n A<\/mml:mi>\n \u2192<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For fixed $$n=\\dim X$$<\/jats:tex-math>\n \n n<\/mml:mi>\n =<\/mml:mo>\n dim<\/mml:mo>\n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf\u2019s theorem, we deduce an algorithm that, given finite simplicial sets X<\/jats:italic>,\u00a0A<\/jats:italic>,\u00a0Y<\/jats:italic> with an action of a finite group\u00a0G<\/jats:italic>, computes the set $$[X,Y]^A_G$$<\/jats:tex-math>\n \n \n [<\/mml:mo>\n X<\/mml:mi>\n ,<\/mml:mo>\n Y<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n G<\/mml:mi>\n A<\/mml:mi>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of homotopy classes of equivariant maps $$\\ell :X\\rightarrow Y$$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n :<\/mml:mo>\n X<\/mml:mi>\n \u2192<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> extending a given equivariant map $$f:A\\rightarrow Y$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n A<\/mml:mi>\n \u2192<\/mml:mo>\n Y<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under the stability assumption $$\\dim X^H\\le 2\\cdot {\\text {conn}}Y^H$$<\/jats:tex-math>\n \n dim<\/mml:mo>\n \n X<\/mml:mi>\n H<\/mml:mi>\n <\/mml:msup>\n \u2264<\/mml:mo>\n 2<\/mml:mn>\n \u00b7<\/mml:mo>\n conn<\/mml:mtext>\n \n Y<\/mml:mi>\n H<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\text {conn}}Y^H\\ge 1$$<\/jats:tex-math>\n \n conn<\/mml:mtext>\n \n Y<\/mml:mi>\n H<\/mml:mi>\n <\/mml:msup>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for all subgroups $$H\\le G$$<\/jats:tex-math>\n \n H<\/mml:mi>\n \u2264<\/mml:mo>\n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Again, for fixed $$n=\\dim X$$<\/jats:tex-math>\n \n n<\/mml:mi>\n =<\/mml:mo>\n dim<\/mml:mo>\n X<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a k<\/jats:italic>-dimensional simplicial complex\u00a0K<\/jats:italic>, is there a map $$K\\rightarrow {\\mathbb {R}}^d$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \u2192<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n d<\/mml:mi>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> without r<\/jats:italic>-tuple intersection points? In the metastable range of dimensions, $$rd\\ge (r+1) k+3$$<\/jats:tex-math>\n \n r<\/mml:mi>\n d<\/mml:mi>\n \u2265<\/mml:mo>\n (<\/mml:mo>\n r<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n k<\/mml:mi>\n +<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the problem is shown algorithmically decidable in polynomial time when k<\/jats:italic>, d<\/jats:italic>, and\u00a0r<\/jats:italic> are fixed.<\/jats:p>","DOI":"10.1007\/s00454-023-00513-0","type":"journal-article","created":{"date-parts":[[2023,7,20]],"date-time":"2023-07-20T20:28:46Z","timestamp":1689884926000},"page":"866-920","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Homotopy Classes for Diagrams"],"prefix":"10.1007","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5978-2623","authenticated-orcid":false,"given":"Marek","family":"Filakovsk\u00fd","sequence":"first","affiliation":[]},{"given":"Luk\u00e1\u0161","family":"Vok\u0159\u00ednek","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,20]]},"reference":[{"issue":"2","key":"513_CR1","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1090\/S0002-9904-1967-11712-9","volume":"73","author":"GE Bredon","year":"1967","unstructured":"Bredon, G.E.: Equivariant cohomology theories. Bull. Am. Math. Soc. 73(2), 266\u2013268 (1967)","journal-title":"Bull. Am. Math. Soc."},{"key":"513_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1969664","volume":"65","author":"EH Brown Jr","year":"1957","unstructured":"Brown, E.H., Jr.: Finite computability of Postnikov complexes. Ann. Math. 65, 1\u201320 (1957)","journal-title":"Ann. Math."},{"key":"513_CR3","doi-asserted-by":"crossref","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Matou\u0161ek, J., Sergeraert, F., Vok\u0159\u00ednek, L., Wagner, U.: Computing all maps into a sphere. J. ACM 61(3), #\u00a017 (2014)","DOI":"10.1145\/2597629"},{"issue":"1","key":"513_CR4","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00454-013-9551-8","volume":"51","author":"M \u010cadek","year":"2014","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Matou\u0161ek, J., Vok\u0159\u00ednek, L., Wagner, U.: Extendability of continuous maps is undecidable. Discrete Comput. Geom. 51(1), 24\u201366 (2014)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"513_CR5","doi-asserted-by":"publisher","first-page":"1728","DOI":"10.1137\/120899029","volume":"43","author":"M \u010cadek","year":"2014","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Matou\u0161ek, J., Vok\u0159\u00ednek, L., Wagner, U.: Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension. SIAM J. Comput. 43(5), 1728\u20131780 (2014)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"513_CR6","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/s00454-016-9855-6","volume":"57","author":"M \u010cadek","year":"2017","unstructured":"\u010cadek, M., Kr\u010d\u00e1l, M., Vok\u0159\u00ednek, L.: Algorithmic solvability of the lifting-extension problem. Discrete Comput. Geom. 57(4), 915\u2013965 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"513_CR7","doi-asserted-by":"publisher","first-page":"55","DOI":"10.2307\/1969820","volume":"58","author":"S Eilenberg","year":"1953","unstructured":"Eilenberg, S., Mac Lane, S.: On the groups $$H(P_{i}, n)$$. I. Ann. Math. 58, 55\u2013106 (1953)","journal-title":"Ann. Math."},{"key":"513_CR8","doi-asserted-by":"publisher","first-page":"49","DOI":"10.2307\/1969702","volume":"60","author":"S Eilenberg","year":"1954","unstructured":"Eilenberg, S., Mac Lane, S.: On the groups $$H(P_{i}, n)$$.\u00a0II. Methods of computation. Ann. Math. 60, 49\u2013139 (1954)","journal-title":"Ann. Math."},{"issue":"1","key":"513_CR9","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1090\/S0002-9947-1983-0690052-0","volume":"277","author":"AD Elmendorf","year":"1983","unstructured":"Elmendorf, A.D.: Systems of fixed point sets. Trans. Am. Math. Soc. 277(1), 275\u2013284 (1983)","journal-title":"Trans. Am. Math. Soc."},{"issue":"5","key":"513_CR10","doi-asserted-by":"publisher","first-page":"273","DOI":"10.5817\/AM2014-5-273","volume":"50","author":"M Filakovsk\u00fd","year":"2014","unstructured":"Filakovsk\u00fd, M.: Effective homology for homotopy colimit and cofibrant replacement. Arch. Math. (Brno) 50(5), 273\u2013286 (2014)","journal-title":"Arch. Math. (Brno)"},{"key":"513_CR11","unstructured":"Filakovsk\u00fd, M.: Algorithmic Construction of the Postnikov Tower for Diagrams of Simplicial Sets. PhD thesis, Masaryk University, Brno (2016). https:\/\/is.muni.cz\/th\/p82ai"},{"issue":"2","key":"513_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10208-019-09419-x","volume":"20","author":"M Filakovsk\u00fd","year":"2020","unstructured":"Filakovsk\u00fd, M., Vok\u0159\u00ednek, L.: Are two given maps homotopic? An algorithmic viewpoint. Found. Comput. Math. 20(2), 311\u2013330 (2020)","journal-title":"Found. Comput. Math."},{"key":"513_CR13","volume-title":"Model Categories. Mathematical Surveys and Monographs","author":"M Hovey","year":"1999","unstructured":"Hovey, M.: Model Categories. Mathematical Surveys and Monographs, vol. 63. American Mathematical Society, Providence (1999)"},{"key":"513_CR14","unstructured":"Mabillard, I., Wagner, U.: Eliminating higher-multiplicity intersections,\u00a0II. The deleted product criterion in the $$r$$-metastable range (2016). arXiv:1601.00876v2"},{"key":"513_CR15","unstructured":"Mabillard, I., Wagner, U.: Eliminating higher-multiplicity intersections,\u00a0II. The deleted product criterion in the $$r$$-metastable range. In: 32nd International Symposium on Computational Geometry (Boston 2016). Leibniz Int. Proc. Inform., vol. 51, #\u00a051. Leibniz-Zent. Inform., Wadern (2016)"},{"key":"513_CR16","volume-title":"Simplicial Objects in Algebraic Topology. Chicago Lectures in Mathematics","author":"JP May","year":"1992","unstructured":"May, J.P.: Simplicial Objects in Algebraic Topology. Chicago Lectures in Mathematics. University of Chicago Press, Chicago (1992)"},{"key":"513_CR17","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/091","volume-title":"Equivariant Homotopy and Cohomology Theory. CBMS Regional Conference Series in Mathematics","author":"JP May","year":"1996","unstructured":"May, J.P., Cole, M., Comeza\u00f1a, G., Costenoble, S., Elmendorf, A.D., Greenlees, J.P.C., Lewis, L.G., Jr., Piacenza, R.J., Triantaflllou, G., Waner, S.: Equivariant Homotopy and Cohomology Theory. CBMS Regional Conference Series in Mathematics, vol. 91. American Mathematical Society, Providence (1996)"},{"key":"513_CR18","unstructured":"Novikov, P.S.: On the Algorithmic Unsolvability of the Word Problem in Group Theory. Trudy Mat. Inst. Steklov., vol. 44. Izdat. Akad. Nauk SSSR, Moscow (1955). (in Russian)"},{"issue":"5","key":"513_CR19","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/S0007-4497(02)01119-3","volume":"126","author":"J Rubio","year":"2002","unstructured":"Rubio, J., Sergeraert, F.: Constructive algebraic topology. Bull. Sci. Math. 126(5), 389\u2013412 (2002)","journal-title":"Bull. Sci. Math."},{"key":"513_CR20","unstructured":"Skopenkov, A.: On the metastable Mabillard\u2013Wagner conjecture (2017). arXiv:1702.04259"},{"key":"513_CR21","unstructured":"Skopenkov, A.: Eliminating higher-mutiplicity intersections in the metastable dimension range (2021). arXiv:1704.00143v3"},{"issue":"5","key":"513_CR22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.5817\/AM2014-5-323","volume":"50","author":"L Vok\u0159\u00ednek","year":"2014","unstructured":"Vok\u0159\u00ednek, L.: Heaps and unpointed stable homotopy theory. Arch. Math. (Brno) 50(5), 323\u2013332 (2014)","journal-title":"Arch. Math. (Brno)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00513-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00513-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00513-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T17:04:46Z","timestamp":1696439086000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00513-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,20]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["513"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00513-0","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,7,20]]},"assertion":[{"value":"24 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}