Nerve Complexes of Circular Arcs

详细信息    查看全文

• 作者：Michał Adamaszek ; Henry Adams ; Florian Frick…
• 刊名：Discrete and Computational Geometry
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：56
• 期：2
• 页码：251-273
• 全文大小：706 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1432-0444
• 卷排序：56

文摘

We show that the nerve and clique complexes of n arcs in the circle are homotopy equivalent to either a point, an odd-dimensional sphere, or a wedge sum of spheres of the same even dimension. Moreover this homotopy type can be computed in time \(O(n\log n)\). For the particular case of the nerve complex of evenly-spaced arcs of the same length, we determine explicit homology bases and we relate the complex to a cyclic polytope with n vertices. We give three applications of our knowledge of the homotopy types of nerve complexes of circular arcs. First, we show that the Lovász bound on the chromatic number of a circular complete graph is either sharp or off by one. Second, we use the connection to cyclic polytopes to give a novel topological proof of a known upper bound on the distance between successive roots of a homogeneous trigonometric polynomial. Third, we show that the Vietoris–Rips or ambient Čech simplicial complex of n points in the circle is homotopy equivalent to either a point, an odd-dimensional sphere, or a wedge sum of spheres of the same even dimension, and furthermore this homotopy type can be computed in time \(O(n\log n)\).KeywordsNerve complexČech complexVietoris–Rips complexCircular arcCyclic polytope