2013/11/30 by Michael Freedman, Vyacheslav Krushkal
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics #Discrete mathematics #Embedding #Euclidean geometry #Euclidean space #Geometric and Algebraic Topology #Geometry #Mathematical analysis #Mathematics #Simplicial complex #Topological and Geometric Data Analysis #Upper and lower bounds #cs.CG #math.CO #math.GT #math.MG
paper · pdf · doi:10.1007/s00039-014-0272-9
published as Geom. Funct. Anal. 24 (2014), no. 5, 1406-1430 · v2: an upper bound is established on refinement complexity for simplicial n-complexes in R^{2n}. Exponential lower bound is extended to a wider range of dimensions. The title is revised to reflect the changes in the paper
arxiv created 2013/12/30 · openalex publication_date 2014/05/05 · arxiv updated 2014/09/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/06
Given a simplicial complex K, we consider several notions of geometric complexity of embeddings of K in a Euclidean space \mathbb Rd: thickness, distortion, and refinement complexity (the minimal number of simplices needed for a PL embedding). We show that any n-complex with N simplices which topologically embeds in \mathbb R2n, n>2, can be PL embedded in \mathbb R2n with refinement complexity O(e^N4+ε). Families of simplicial n-complexes K are constructed such that any embedding of K into \mathbb R2n has an exponential lower bound on thickness and refinement complexity as a function of the number of simplices of K. This contrasts embeddings in the stable range, K⊂ \mathbb R2n+k, k>0, where all known bounds on geometric complexity functions are polynomial. In addition, we give a geometric argument for a bound on distortion of expander graphs in Euclidean spaces. Several related open problems are discussed, including questions about the growth rate of complexity functions of embeddings, and about the crossing number and the ropelength of classical links.