--- _id: '13331' abstract: - lang: eng text: "The extension of extremal combinatorics to the setting of exterior algebra is a work\r\nin progress that gained attention recently. In this thesis, we study the combinatorial structure of exterior algebra by introducing a dictionary that translates the notions from the set systems into the framework of exterior algebra. We show both generalizations of celebrated Erdös--Ko--Rado theorem and Hilton--Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms.\r\n" alternative_title: - ISTA Master's Thesis article_processing_charge: No author: - first_name: Seyda full_name: Köse, Seyda id: 8ba3170d-dc85-11ea-9058-c4251c96a6eb last_name: Köse citation: ama: Köse S. Exterior algebra and combinatorics. 2023. doi:10.15479/at:ista:13331 apa: Köse, S. (2023). Exterior algebra and combinatorics. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:13331 chicago: Köse, Seyda. “Exterior Algebra and Combinatorics.” Institute of Science and Technology Austria, 2023. https://doi.org/10.15479/at:ista:13331. ieee: S. Köse, “Exterior algebra and combinatorics,” Institute of Science and Technology Austria, 2023. ista: Köse S. 2023. Exterior algebra and combinatorics. Institute of Science and Technology Austria. mla: Köse, Seyda. Exterior Algebra and Combinatorics. Institute of Science and Technology Austria, 2023, doi:10.15479/at:ista:13331. short: S. Köse, Exterior Algebra and Combinatorics, Institute of Science and Technology Austria, 2023. date_created: 2023-07-31T10:20:55Z date_published: 2023-07-31T00:00:00Z date_updated: 2023-10-04T11:54:56Z day: '31' ddc: - '510' - '516' degree_awarded: MS department: - _id: GradSch - _id: UlWa doi: 10.15479/at:ista:13331 file: - access_level: closed checksum: 96ee518d796d02af71395622c45de03c content_type: application/x-zip-compressed creator: skoese date_created: 2023-07-31T10:16:32Z date_updated: 2023-07-31T10:16:32Z file_id: '13333' file_name: Exterior Algebra and Combinatorics.zip file_size: 28684 relation: source_file - access_level: open_access checksum: f610f4713f88bc477de576aaa46b114e content_type: application/pdf creator: skoese date_created: 2023-08-03T15:28:55Z date_updated: 2023-08-03T15:28:55Z file_id: '13480' file_name: thesis-pdfa.pdf file_size: 4953418 relation: main_file success: 1 file_date_updated: 2023-08-03T15:28:55Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '26' publication_identifier: issn: - 2791-4585 publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '12680' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 title: Exterior algebra and combinatorics type: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2023' ... --- _id: '11777' abstract: - lang: eng text: "In this dissertation we study coboundary expansion of simplicial complex with a view of giving geometric applications.\r\nOur main novel tool is an equivariant version of Gromov's celebrated Topological Overlap Theorem. The equivariant topological overlap theorem leads to various geometric applications including a quantitative non-embeddability result for sufficiently thick buildings (which partially resolves a conjecture of Tancer and Vorwerk) and an improved lower bound on the pair-crossing number of (bounded degree) expander graphs. Additionally, we will give new proofs for several known lower bounds for geometric problems such as the number of Tverberg partitions or the crossing number of complete bipartite graphs.\r\nFor the aforementioned applications one is naturally lead to study expansion properties of joins of simplicial complexes. In the presence of a special certificate for expansion (as it is the case, e.g., for spherical buildings), the join of two expanders is an expander. On the flip-side, we report quite some evidence that coboundary expansion exhibits very non-product-like behaviour under taking joins. For instance, we exhibit infinite families of graphs $(G_n)_{n\\in \\mathbb{N}}$ and $(H_n)_{n\\in\\mathbb{N}}$ whose join $G_n*H_n$ has expansion of lower order than the product of the expansion constant of the graphs. Moreover, we show an upper bound of $(d+1)/2^d$ on the normalized coboundary expansion constants for the complete multipartite complex $[n]^{*(d+1)}$ (under a mild divisibility condition on $n$).\r\nVia the probabilistic method the latter result extends to an upper bound of $(d+1)/2^d+\\varepsilon$ on the coboundary expansion constant of the spherical building associated with $\\mathrm{PGL}_{d+2}(\\mathbb{F}_q)$ for any $\\varepsilon>0$ and sufficiently large $q=q(\\varepsilon)$. This disproves a conjecture of Lubotzky, Meshulam and Mozes -- in a rather strong sense.\r\nBy improving on existing lower bounds we make further progress towards closing the gap between the known lower and upper bounds on the coboundary expansion constants of $[n]^{*(d+1)}$. The best improvements we achieve using computer-aided proofs and flag algebras. The exact value even for the complete $3$-partite $2$-dimensional complex $[n]^{*3}$ remains unknown but we are happy to conjecture a precise value for every $n$. %Moreover, we show that a previously shown lower bound on the expansion constant of the spherical building associated with $\\mathrm{PGL}_{2}(\\mathbb{F}_q)$ is not tight.\r\nIn a loosely structured, last chapter of this thesis we collect further smaller observations related to expansion. We point out a link between discrete Morse theory and a technique for showing coboundary expansion, elaborate a bit on the hardness of computing coboundary expansion constants, propose a new criterion for coboundary expansion (in a very dense setting) and give one way of making the folklore result that expansion of links is a necessary condition for a simplicial complex to be an expander precise." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Pascal full_name: Wild, Pascal id: 4C20D868-F248-11E8-B48F-1D18A9856A87 last_name: Wild citation: ama: Wild P. High-dimensional expansion and crossing numbers of simplicial complexes. 2022. doi:10.15479/at:ista:11777 apa: Wild, P. (2022). High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology. https://doi.org/10.15479/at:ista:11777 chicago: Wild, Pascal. “High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes.” Institute of Science and Technology, 2022. https://doi.org/10.15479/at:ista:11777. ieee: P. Wild, “High-dimensional expansion and crossing numbers of simplicial complexes,” Institute of Science and Technology, 2022. ista: Wild P. 2022. High-dimensional expansion and crossing numbers of simplicial complexes. Institute of Science and Technology. mla: Wild, Pascal. High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes. Institute of Science and Technology, 2022, doi:10.15479/at:ista:11777. short: P. Wild, High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes, Institute of Science and Technology, 2022. date_created: 2022-08-10T15:51:19Z date_published: 2022-08-11T00:00:00Z date_updated: 2023-06-22T09:56:36Z day: '11' ddc: - '500' - '516' - '514' degree_awarded: PhD department: - _id: GradSch - _id: UlWa doi: 10.15479/at:ista:11777 ec_funded: 1 file: - access_level: open_access checksum: f5f3af1fb7c8a24b71ddc88ad7f7c5b4 content_type: text/x-python creator: pwild date_created: 2022-08-10T15:34:04Z date_updated: 2022-08-10T15:34:04Z description: Code for computer-assisted proofs in Section 8.4.7 in Thesis file_id: '11780' file_name: flags.py file_size: 16828 relation: supplementary_material - access_level: open_access checksum: 1f7c12dfe3bdaa9b147e4fbc3d34e3d5 content_type: text/x-c++src creator: pwild date_created: 2022-08-10T15:34:10Z date_updated: 2022-08-10T15:34:10Z description: Code for proof of Lemma 8.20 in Thesis file_id: '11781' file_name: lowerbound.cpp file_size: 12226 relation: supplementary_material - access_level: open_access checksum: 4cf81455c49e5dec3b9b2e3980137eeb content_type: text/x-python creator: pwild date_created: 2022-08-10T15:34:17Z date_updated: 2022-08-10T15:34:17Z description: Code for proof of Proposition 7.9 in Thesis file_id: '11782' file_name: upperbound.py file_size: 3240 relation: supplementary_material - access_level: open_access checksum: 4e96575b10cbe4e0d0db2045b2847774 content_type: application/pdf creator: pwild date_created: 2022-08-11T16:08:33Z date_updated: 2022-08-11T16:08:33Z file_id: '11809' file_name: finalthesisPascalWildPDFA.pdf file_size: 5086282 relation: main_file title: High-Dimensional Expansion and Crossing Numbers of Simplicial Complexes - access_level: closed checksum: 92d94842a1fb6dca5808448137573b2e content_type: application/zip creator: pwild date_created: 2022-08-11T16:09:19Z date_updated: 2022-08-11T16:09:19Z file_id: '11810' file_name: ThesisSubmission.zip file_size: 18150068 relation: source_file file_date_updated: 2022-08-11T16:09:19Z has_accepted_license: '1' language: - iso: eng month: '08' oa: 1 oa_version: Published Version page: '170' project: - _id: 2564DBCA-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '665385' name: International IST Doctoral Program publication_identifier: isbn: - 978-3-99078-021-3 issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 title: High-dimensional expansion and crossing numbers of simplicial complexes type: dissertation user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 year: '2022' ... --- _id: '7944' abstract: - lang: eng text: "This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Zuzana full_name: Masárová, Zuzana id: 45CFE238-F248-11E8-B48F-1D18A9856A87 last_name: Masárová orcid: 0000-0002-6660-1322 citation: ama: Masárová Z. Reconfiguration problems. 2020. doi:10.15479/AT:ISTA:7944 apa: Masárová, Z. (2020). Reconfiguration problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7944 chicago: Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7944. ieee: Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020. ista: Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria. mla: Masárová, Zuzana. Reconfiguration Problems. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7944. short: Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020. date_created: 2020-06-08T00:49:46Z date_published: 2020-06-09T00:00:00Z date_updated: 2023-09-07T13:17:37Z day: '09' ddc: - '516' - '514' degree_awarded: PhD department: - _id: HeEd - _id: UlWa doi: 10.15479/AT:ISTA:7944 file: - access_level: open_access checksum: df688bc5a82b50baee0b99d25fc7b7f0 content_type: application/pdf creator: zmasarov date_created: 2020-06-08T00:34:00Z date_updated: 2020-07-14T12:48:05Z file_id: '7945' file_name: THESIS_Zuzka_Masarova.pdf file_size: 13661779 relation: main_file - access_level: closed checksum: 45341a35b8f5529c74010b7af43ac188 content_type: application/zip creator: zmasarov date_created: 2020-06-08T00:35:30Z date_updated: 2020-07-14T12:48:05Z file_id: '7946' file_name: THESIS_Zuzka_Masarova_SOURCE_FILES.zip file_size: 32184006 relation: source_file file_date_updated: 2020-07-14T12:48:05Z has_accepted_license: '1' keyword: - reconfiguration - reconfiguration graph - triangulations - flip - constrained triangulations - shellability - piecewise-linear balls - token swapping - trees - coloured weighted token swapping language: - iso: eng license: https://creativecommons.org/licenses/by-sa/4.0/ month: '06' oa: 1 oa_version: Published Version page: '160' publication_identifier: isbn: - 978-3-99078-005-3 issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '7950' relation: part_of_dissertation status: public - id: '5986' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 title: Reconfiguration problems tmp: image: /images/cc_by_sa.png legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0) short: CC BY-SA (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ... --- _id: '8032' abstract: - lang: eng text: "Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus." acknowledged_ssus: - _id: E-Lib - _id: CampIT alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Kristóf full_name: Huszár, Kristóf id: 33C26278-F248-11E8-B48F-1D18A9856A87 last_name: Huszár orcid: 0000-0002-5445-5057 citation: ama: Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:10.15479/AT:ISTA:8032 apa: Huszár, K. (2020). Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8032 chicago: Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8032. ieee: K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020. ista: Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria. mla: Huszár, Kristóf. Combinatorial Width Parameters for 3-Dimensional Manifolds. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8032. short: K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020. date_created: 2020-06-26T10:00:36Z date_published: 2020-06-26T00:00:00Z date_updated: 2023-09-07T13:18:27Z day: '26' ddc: - '514' degree_awarded: PhD department: - _id: UlWa doi: 10.15479/AT:ISTA:8032 file: - access_level: open_access checksum: bd8be6e4f1addc863dfcc0fad29ee9c3 content_type: application/pdf creator: khuszar date_created: 2020-06-26T10:03:58Z date_updated: 2020-07-14T12:48:08Z file_id: '8034' file_name: Kristof_Huszar-Thesis.pdf file_size: 2637562 relation: main_file - access_level: closed checksum: d5f8456202b32f4a77552ef47a2837d1 content_type: application/x-zip-compressed creator: khuszar date_created: 2020-06-26T10:10:06Z date_updated: 2020-07-14T12:48:08Z file_id: '8035' file_name: Kristof_Huszar-Thesis-source.zip file_size: 7163491 relation: source_file file_date_updated: 2020-07-14T12:48:08Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: xviii+120 publication_identifier: isbn: - 978-3-99078-006-0 issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '6556' relation: dissertation_contains status: public - id: '7093' relation: dissertation_contains status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 - first_name: Jonathan full_name: Spreer, Jonathan last_name: Spreer title: Combinatorial width parameters for 3-dimensional manifolds tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ... --- _id: '8156' abstract: - lang: eng text: 'We present solutions to several problems originating from geometry and discrete mathematics: existence of equipartitions, maps without Tverberg multiple points, and inscribing quadrilaterals. Equivariant obstruction theory is the natural topological approach to these type of questions. However, for the specific problems we consider it had yielded only partial or no results. We get our results by complementing equivariant obstruction theory with other techniques from topology and geometry.' alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Sergey full_name: Avvakumov, Sergey id: 3827DAC8-F248-11E8-B48F-1D18A9856A87 last_name: Avvakumov citation: ama: Avvakumov S. Topological methods in geometry and discrete mathematics. 2020. doi:10.15479/AT:ISTA:8156 apa: Avvakumov, S. (2020). Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:8156 chicago: Avvakumov, Sergey. “Topological Methods in Geometry and Discrete Mathematics.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:8156. ieee: S. Avvakumov, “Topological methods in geometry and discrete mathematics,” Institute of Science and Technology Austria, 2020. ista: Avvakumov S. 2020. Topological methods in geometry and discrete mathematics. Institute of Science and Technology Austria. mla: Avvakumov, Sergey. Topological Methods in Geometry and Discrete Mathematics. Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:8156. short: S. Avvakumov, Topological Methods in Geometry and Discrete Mathematics, Institute of Science and Technology Austria, 2020. date_created: 2020-07-23T09:51:29Z date_published: 2020-07-24T00:00:00Z date_updated: 2023-12-18T10:51:01Z day: '24' ddc: - '514' degree_awarded: PhD department: - _id: UlWa doi: 10.15479/AT:ISTA:8156 file: - access_level: closed content_type: application/zip creator: savvakum date_created: 2020-07-27T12:44:51Z date_updated: 2020-07-27T12:44:51Z file_id: '8178' file_name: source.zip file_size: 1061740 relation: source_file - access_level: open_access content_type: application/pdf creator: savvakum date_created: 2020-07-27T12:46:53Z date_updated: 2020-07-27T12:46:53Z file_id: '8179' file_name: thesis_pdfa.pdf file_size: 1336501 relation: main_file success: 1 file_date_updated: 2020-07-27T12:46:53Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '119' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '8182' relation: part_of_dissertation status: public - id: '8183' relation: part_of_dissertation status: public - id: '8185' relation: part_of_dissertation status: public - id: '8184' relation: part_of_dissertation status: public - id: '6355' relation: part_of_dissertation status: public - id: '75' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 title: Topological methods in geometry and discrete mathematics type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2020' ... --- _id: '6681' abstract: - lang: eng text: "The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2.\r\nHowever, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2,\r\nwe construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X).\r\nIn the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Stephan Y full_name: Zhechev, Stephan Y id: 3AA52972-F248-11E8-B48F-1D18A9856A87 last_name: Zhechev citation: ama: Zhechev SY. Algorithmic aspects of homotopy theory and embeddability. 2019. doi:10.15479/AT:ISTA:6681 apa: Zhechev, S. Y. (2019). Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:6681 chicago: Zhechev, Stephan Y. “Algorithmic Aspects of Homotopy Theory and Embeddability.” Institute of Science and Technology Austria, 2019. https://doi.org/10.15479/AT:ISTA:6681. ieee: S. Y. Zhechev, “Algorithmic aspects of homotopy theory and embeddability,” Institute of Science and Technology Austria, 2019. ista: Zhechev SY. 2019. Algorithmic aspects of homotopy theory and embeddability. Institute of Science and Technology Austria. mla: Zhechev, Stephan Y. Algorithmic Aspects of Homotopy Theory and Embeddability. Institute of Science and Technology Austria, 2019, doi:10.15479/AT:ISTA:6681. short: S.Y. Zhechev, Algorithmic Aspects of Homotopy Theory and Embeddability, Institute of Science and Technology Austria, 2019. date_created: 2019-07-26T11:14:34Z date_published: 2019-08-08T00:00:00Z date_updated: 2023-09-07T13:10:36Z day: '08' ddc: - '514' degree_awarded: PhD department: - _id: UlWa doi: 10.15479/AT:ISTA:6681 file: - access_level: open_access checksum: 3231e7cbfca3b5687366f84f0a57a0c0 content_type: application/pdf creator: szhechev date_created: 2019-08-07T13:02:50Z date_updated: 2020-07-14T12:47:37Z file_id: '6771' file_name: Stephan_Zhechev_thesis.pdf file_size: 1464227 relation: main_file - access_level: closed checksum: 85d65eb27b4377a9e332ee37a70f08b6 content_type: application/octet-stream creator: szhechev date_created: 2019-08-07T13:03:22Z date_updated: 2020-07-14T12:47:37Z file_id: '6772' file_name: Stephan_Zhechev_thesis.tex file_size: 303988 relation: source_file - access_level: closed checksum: 86b374d264ca2dd53e712728e253ee75 content_type: application/zip creator: szhechev date_created: 2019-08-07T13:03:34Z date_updated: 2020-07-14T12:47:37Z file_id: '6773' file_name: supplementary_material.zip file_size: 1087004 relation: supplementary_material file_date_updated: 2020-07-14T12:47:37Z has_accepted_license: '1' language: - iso: eng month: '08' oa: 1 oa_version: Published Version page: '104' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria related_material: record: - id: '6774' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 title: Algorithmic aspects of homotopy theory and embeddability tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2019' ... --- _id: '1123' abstract: - lang: eng text: "Motivated by topological Tverberg-type problems in topological combinatorics and by classical\r\nresults about embeddings (maps without double points), we study the question whether a finite\r\nsimplicial complex K can be mapped into Rd without triple, quadruple, or, more generally, r-fold points (image points with at least r distinct preimages), for a given multiplicity r ≤ 2. In particular, we are interested in maps f : K → Rd that have no global r -fold intersection points, i.e., no r -fold points with preimages in r pairwise disjoint simplices of K , and we seek necessary and sufficient conditions for the existence of such maps.\r\n\r\nWe present higher-multiplicity analogues of several classical results for embeddings, in particular of the completeness of the Van Kampen obstruction \ for embeddability of k -dimensional\r\ncomplexes into R2k , k ≥ 3. Speciffically, we show that under suitable restrictions on the dimensions(viz., if dimK = (r ≥ 1)k and d = rk \\ for some k ≥ 3), a well-known deleted product criterion (DPC ) is not only necessary but also sufficient for the existence of maps without global r -fold points. Our main technical tool is a higher-multiplicity version of the classical Whitney trick , by which pairs of isolated r -fold points of opposite sign can be eliminated by local modiffications of the map, assuming codimension d – dimK ≥ 3.\r\n\r\nAn important guiding idea for our work was that suffciency of the DPC, together with an old\r\nresult of Özaydin's on the existence of equivariant maps, might yield an approach to disproving the remaining open cases of the the long-standing topological Tverberg conjecture , i.e., to construct maps from the N -simplex σN to Rd without r-Tverberg points when r not a prime power and\r\nN = (d + 1)(r – 1). Unfortunately, our proof of the sufficiency of the DPC requires codimension d – dimK ≥ 3, which is not satisfied for K = σN .\r\n\r\nIn 2015, Frick [16] found a very elegant way to overcome this \\codimension 3 obstacle" and\r\nto construct the first counterexamples to the topological Tverberg conjecture for all parameters(d; r ) with d ≥ 3r + 1 and r not a prime power, by a reduction1 to a suitable lower-dimensional skeleton, for which the codimension 3 restriction is satisfied and maps without r -Tverberg points exist by Özaydin's result and sufficiency of the DPC.\r\n\r\nIn this thesis, we present a different construction (which does not use the constraint method) that yields counterexamples for d ≥ 3r , r not a prime power. " acknowledgement: "Foremost, I would like to thank Uli Wagner for introducing me to the exciting interface between\r\ntopology and combinatorics, and for our subsequent years of fruitful collaboration.\r\nIn our creative endeavors to eliminate intersection points, we had the chance to be joined later\r\nby Sergey Avvakumov and Arkadiy Skopenkov, which led us to new surprises in dimension 12.\r\nMy stay at EPFL and IST Austria was made very agreeable thanks to all these wonderful\r\npeople: Cyril Becker, Marek Filakovsky, Peter Franek, Radoslav Fulek, Peter Gazi, Kristof Huszar,\r\nMarek Krcal, Zuzana Masarova, Arnaud de Mesmay, Filip Moric, Michal Rybar, Martin Tancer,\r\nand Stephan Zhechev.\r\nFinally, I would like to thank my thesis committee Herbert Edelsbrunner and Roman Karasev\r\nfor their careful reading of the present manuscript and for the many improvements they suggested." alternative_title: - ISTA Thesis article_processing_charge: No author: - first_name: Isaac full_name: Mabillard, Isaac id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87 last_name: Mabillard citation: ama: 'Mabillard I. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. 2016.' apa: 'Mabillard, I. (2016). Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. Institute of Science and Technology Austria.' chicago: 'Mabillard, Isaac. “Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture.” Institute of Science and Technology Austria, 2016.' ieee: 'I. Mabillard, “Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture,” Institute of Science and Technology Austria, 2016.' ista: 'Mabillard I. 2016. Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture. Institute of Science and Technology Austria.' mla: 'Mabillard, Isaac. Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture. Institute of Science and Technology Austria, 2016.' short: 'I. Mabillard, Eliminating Higher-Multiplicity Intersections: An r-Fold Whitney Trick for the Topological Tverberg Conjecture, Institute of Science and Technology Austria, 2016.' date_created: 2018-12-11T11:50:16Z date_published: 2016-08-01T00:00:00Z date_updated: 2023-09-07T11:56:28Z day: '01' ddc: - '500' degree_awarded: PhD department: - _id: UlWa file: - access_level: closed checksum: 2d140cc924cd1b764544906fc22684ef content_type: application/pdf creator: dernst date_created: 2019-08-13T08:45:27Z date_updated: 2019-08-13T08:45:27Z file_id: '6809' file_name: Thesis_final version_Mabillard_w_signature_page.pdf file_size: 2227916 relation: main_file - access_level: open_access checksum: 2d140cc924cd1b764544906fc22684ef content_type: application/pdf creator: dernst date_created: 2021-02-22T11:36:34Z date_updated: 2021-02-22T11:36:34Z file_id: '9178' file_name: 2016_Mabillard_Thesis.pdf file_size: 2227916 relation: main_file success: 1 file_date_updated: 2021-02-22T11:36:34Z has_accepted_license: '1' language: - iso: eng month: '08' oa: 1 oa_version: Published Version page: '55' publication_identifier: issn: - 2663-337X publication_status: published publisher: Institute of Science and Technology Austria publist_id: '6237' related_material: record: - id: '2159' relation: part_of_dissertation status: public status: public supervisor: - first_name: Uli full_name: Wagner, Uli id: 36690CA2-F248-11E8-B48F-1D18A9856A87 last_name: Wagner orcid: 0000-0002-1494-0568 title: 'Eliminating higher-multiplicity intersections: an r-fold Whitney trick for the topological Tverberg conjecture' type: dissertation user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2016' ...