Nerve Complexes of Circular Arcs.

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)$$ . [ABSTRACT FROM AUTHOR]