Lifting maps between graphs to embeddings
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912534816096256 |
|---|---|
| author | Gorelov, Alexey |
| author_facet | Gorelov, Alexey |
| contents | In this paper, we study conditions for the existence of an embedding $\widetilde{f} \colon P \to Q \times \mathbb{R}$ such that $f = \mathrm{pr}_Q \circ \widetilde{f}$, where $f \colon P \to Q$ is a piecewise linear map between polyhedra. Our focus is on non-degenerate maps between graphs, where non-degeneracy means that the preimages of points are finite sets.
We introduce combinatorial techniques and establish necessary and sufficient conditions for the general case. Using these results, we demonstrate that the problem of the existence of a lifting reduces to testing the satisfiability of a 3-CNF formula. Additionally, we construct a counterexample to a result by V. Poénaru on lifting of smooth immersions to embeddings.
Furthermore, by establishing connections between the stated problem and the approximability by embeddings, we deduce that, in the case of generic maps from a tree to a segment, a weaker condition becomes sufficient for the existence of a lifting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12287 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lifting maps between graphs to embeddings Gorelov, Alexey Geometric Topology Computational Geometry Discrete Mathematics Combinatorics 05C10, 57M15, 57Q35 (Primary), 57N35, 05E45 (Secondary) In this paper, we study conditions for the existence of an embedding $\widetilde{f} \colon P \to Q \times \mathbb{R}$ such that $f = \mathrm{pr}_Q \circ \widetilde{f}$, where $f \colon P \to Q$ is a piecewise linear map between polyhedra. Our focus is on non-degenerate maps between graphs, where non-degeneracy means that the preimages of points are finite sets. We introduce combinatorial techniques and establish necessary and sufficient conditions for the general case. Using these results, we demonstrate that the problem of the existence of a lifting reduces to testing the satisfiability of a 3-CNF formula. Additionally, we construct a counterexample to a result by V. Poénaru on lifting of smooth immersions to embeddings. Furthermore, by establishing connections between the stated problem and the approximability by embeddings, we deduce that, in the case of generic maps from a tree to a segment, a weaker condition becomes sufficient for the existence of a lifting. |
| title | Lifting maps between graphs to embeddings |
| topic | Geometric Topology Computational Geometry Discrete Mathematics Combinatorics 05C10, 57M15, 57Q35 (Primary), 57N35, 05E45 (Secondary) |
| url | https://arxiv.org/abs/2404.12287 |