Lifting maps between graphs to embeddings
Alexey Gorelov
在本文中,我们研究了嵌入f P → Q ×R的存在条件,使f = pr_Q ∘f,其中f P → Q是polyhedra之间的分段线性映射。 我们的重点是图形之间的非退化映射,其中非退行性意味着点的预成像是有限集。 我们引入组合技术,并为一般情况建立必要和充分的条件。 使用这些结果,我们证明提升存在的问题减少了测试3-CNF公式的可满足性。 此外,我们通过 V 构造一个反例给结果。 Poénaru关于将平滑浸入到嵌入。 此外,通过嵌入在所述问题与近似值之间建立连接,我们推断,在从树到段的通用地图的情况下,较弱的条件足以存在提升。
In this paper, we study conditions for the existence of an embedding f P → Q ×ℝ such that f = pr_Q ∘f, where f P → 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 t...
