×

Nerve complexes of circular arcs. (English) Zbl 1354.05149

The main result of this paper, Theorem 5.4, states that both the nerve complex and clique complex of a finite collection of arcs in the circle are homotopy equivalent to either a point, a sphere of odd dimension, or a wedge sum of spheres of the same even dimension. This is an interesting first step away from the hypotheses of the nerve theorem.
The proof builds up through the special case of evenly spaced arcs, for which there is a concise summary in Sections 3 and 4. The general case is tackled in Section 5.
Section 6 contains a nice application to a result of Lovász that the chromatic number of a graph is at least 3 more than the connectivity number of its neighbourhood complex. A certain circulant graph connected with the circular chromatic number is shown to exceed this bound by at most one.
The exposition is very clear and is aided with some helpful diagrams.

MSC:

05E45 Combinatorial aspects of simplicial complexes
05C40 Connectivity
05C15 Coloring of graphs and hypergraphs
55U10 Simplicial sets and complexes in algebraic topology
55P15 Classification of homotopy type
52B15 Symmetry properties of polytopes
68R05 Combinatorics in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adamaszek, M.: Clique complexes and graph powers. Isr. J. Math. 196(1), 295-319 (2013) · Zbl 1275.05041 · doi:10.1007/s11856-012-0166-1
[2] Adamaszek, M., Adams, H.: The Vietoris-Rips complex of the circle. Preprint, arXiv:1503.03669 · Zbl 1366.05124
[3] Adamaszek, M., Adams, H., Motta, F.: Random cyclic dynamical systems. Preprint, arXiv:1511.07832 · Zbl 1379.37011
[4] Attali, D., Lieutier, A.: Geometry driven collapses for converting a Čech complex into a triangulation of a shape. Discrete Comput. Geom. 54(4), 798-825 (2014) · Zbl 1336.68258 · doi:10.1007/s00454-015-9733-7
[5] Attali, D., Lieutier, A., Salinas, D.: Vietoris-Rips complexes also provide topologically correct reconstructions of sampled shapes. Comput. Geom. 46(4), 448-465 (2013) · Zbl 1262.68171 · doi:10.1016/j.comgeo.2012.02.009
[6] Babenko, A.G.: An extremal problem for polynomials. Math. Notes 35(3), 181-186 (1984) · Zbl 0601.41028 · doi:10.1007/BF01139914
[7] Babson, E., Kozlov, D.N.: Complexes of graph homomorphisms. Isr. J. Math. 152(1), 285-312 (2006) · Zbl 1205.52009 · doi:10.1007/BF02771988
[8] Bagchi, B., Datta, B.: Minimal triangulations of sphere bundles over the circle. J. Comb. Theory, Ser. A 115(5), 737-752 (2008) · Zbl 1146.52007 · doi:10.1016/j.jcta.2007.09.005
[9] Barmak, J.A.: On Quillen’s Theorem A for posets. J. Comb. Theory, Ser. A 118(8), 2445-2453 (2011) · Zbl 1234.05237 · doi:10.1016/j.jcta.2011.06.008
[10] Barmak, J.A., Minian, E.G.: Strong homotopy types, nerves and collapses. Discrete Comput. Geom. 47(2), 301-328 (2012) · Zbl 1242.57019 · doi:10.1007/s00454-011-9357-5
[11] Björner, A.: Topological Methods. Handbook of Combinatorics, vol. 2. Elsevier, Amsterdam (1995)
[12] Borsuk, K.: On the imbedding of systems of compacta in simplicial complexes. Fundam. Math. 35(1), 217-234 (1948) · Zbl 0032.12303
[13] Carlsson, G.: Topology and data. Bull. Am. Math. Soc. 46(2), 255-308 (2009) · Zbl 1172.62002 · doi:10.1090/S0273-0979-09-01249-X
[14] Chazal, F., de Silva, V., Oudot, S.: Persistence stability for geometric complexes. Geom. Dedicata 173(1), 193-214 (2013) · Zbl 1320.55003 · doi:10.1007/s10711-013-9937-z
[15] Chazal, F., Oudot, S.: Towards persistence-based reconstruction in Euclidean spaces. In: Proceedings of the 24th Annual Symposium on Computational Geometry, pp. 232-241. ACM, New York (2008) · Zbl 1271.57058
[16] Colin de Verdière, É., Ginot, G., Goaoc, X.: Multinerves and Helly numbers of acyclic families. In: Proceedings of the 28th Annual Symposium on Computational Geometry, pp. 209-218. ACM, New York (2012) · Zbl 1293.68286
[17] Edelsbrunner, H., Harer, J.L.: Computational Topology: An Introduction. American Mathematical Society, Providence (2010) · Zbl 1193.55001
[18] Gale, D.: Neighborly and cyclic polytopes. Proc. Symp. Pure Math. 7, 225-232 (1963) · Zbl 0137.41801 · doi:10.1090/pspum/007/0152944
[19] Gilbert, A.D., Smyth, C.J.: Zero-mean cosine polynomials which are non-negative for as long as possible. J. Lond. Math. Soc. 62(2), 489-504 (2000) · Zbl 1032.42002 · doi:10.1112/S0024610700001216
[20] Golumbic, M.C., Hammer, P.L.: Stability in circular arc graphs. J. Algorithms 9(3), 314-320 (1988) · Zbl 0651.68083 · doi:10.1016/0196-6774(88)90023-5
[21] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002) · Zbl 1044.55001
[22] Hell, P., Nešetřil, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004) · Zbl 1062.05139 · doi:10.1093/acprof:oso/9780198528173.001.0001
[23] Kozlov, D.N.: Combinatorial Algebraic Topology. Algorithms and Computation in Mathematics, vol. 21. Springer, Berlin (2008) · Zbl 1130.55001
[24] Kozma, G., Oravecz, F.: On the gaps between zeros of trigonometric polynomials. Real Anal. Exch. 28(2), 447-454 (2002) · Zbl 1050.42001
[25] Kühnel, W.: Higherdimensional analogues of Császár’s torus. Result. Math. 9, 95-106 (1986) · Zbl 0552.52003 · doi:10.1007/BF03322352
[26] Kühnel, W., Lassmann, G.: Permuted difference cycles and triangulated sphere bundles. Discrete Math. 162(1-3), 215-227 (1996) · Zbl 0866.52011 · doi:10.1016/0012-365X(95)00287-7
[27] Latschev, J.: Vietoris-Rips complexes of metric spaces near a closed Riemannian manifold. Arch. Math. 77(6), 522-528 (2001) · Zbl 1001.53026 · doi:10.1007/PL00000526
[28] Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A 25(3), 319-324 (1978) · Zbl 0418.05028 · doi:10.1016/0097-3165(78)90022-5
[29] Matoušek, J.: LC reductions yield isomorphic simplicial complexes. Contrib. Discrete Math. 3(2), 37-39 (2008) · Zbl 1191.52011
[30] Montgomery, H.L., Ulrike, M.A.: Biased trigonometric polynomials. Am. Math. Mon. 114(9), 804-809 (2007) · Zbl 1268.42001
[31] Previte-Johnson, C.: The \[D\] D-Neighborhood Complex of a Graph. PhD thesis, Colorado State University, Fort Collins (2014)
[32] Taylan, D.: Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs. Order (2015). doi:10.1007/s11083-015-9379-3 · Zbl 1353.05133
[33] Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, Berlin (1995) · Zbl 0823.52002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.