×

Helly numbers of acyclic families. (English) Zbl 1301.52019

The Helly number \(\text{h}(\mathcal F)\) of a family of sets \(\mathcal F\) with empty intersection (i.e. \(\bigcap_{X\in \mathcal F} X= \emptyset\)) is the largest cardinal of a sub-family \({\mathcal A}\subset \mathcal F\) of empty intersection such that any proper sub-family \(\mathcal B\) of \(\mathcal A\) has non-empty intersection. Ed. Helly’s theorem [Jahresber. Dtsch. Math.-Ver. 32, 175–176 (1923; JFM 49.0534.02)] can be formulated by saying that any finite family of convex sets in \({\mathbb R}^d\) has Helly number at most \(d+1\). In this paper, the authors generalizes this type of results by allowing certain families with disconnected intersections.
Let \(\mathcal F\) be a finite family of open subsets (with empty intersection) of a locally arc-wise connected topological space \(\Gamma\).
The nerve \(\mathcal N(\mathcal F)\) of \(\mathcal F\) is the simplicial complex obtained by associating a \(k\)-dimensional simplex to every sub-family of cardinal \((k+1)\) and with non-empty intersection. When \(\mathcal F\) is a good cover, the nerve captures the topology of the union of the sets (i.e. \({\mathcal N}(\mathcal F)\) and \(\bigcup_{X\in \mathcal F} X\) have the same homotopy type, see A. Björner [in: Handbook of combinatorics. Vol. 1–2. Amsterdam: Elsevier (North-Holland). 1819–1872 (1995; Zbl 0851.52016)]) but this is no longer true with families having disconnected intersections, and the authors introduce the multinerve \(\mathcal M(\mathcal F)\) of \(\mathcal F\) which conserves more information than \(\mathcal N(\mathcal F)\): by definition, the multinerve associates to each sub-family of \(\mathcal F\) of cardinal \((k+1)\) with non-empty intersection a number of \(k\)-dimensional simplices equal to the number of connected components of the intersection of the sub-family. The multinerve has a structure of simplicial poset and there is a natural projection from the multinerve to the nerve.
Generalizing the nerve theorem, the authors get a homological multinerve theorem which, for acyclic families (a family \(\mathcal F\) is acyclic if the intersection of every non-empty sub-family has trivial \(\mathbb Q\)-homology in dimension larger than zero; in particular, the intersection needs not be connected), states that \(\bigcup_{X\in \mathcal F} X\) has the same reduced homology as \(\mathcal M(\mathcal F)\). Actually, the homological multinerve theorem is far more general, stating that \(\widetilde{H}_i(\mathcal M(\mathcal F)) \cong \widetilde{H}_i(\bigcup_{X\in \mathcal F} X)\) for \(i=0\) and \(i\geq s\) if the family is acyclic with slack s (acyclicity with slack – a notion introduced by S. Hell in [“On a topological fractional Helly theorem”, arXiv:math/0506399] – allows non trivial homology in low dimension: the family \(\mathcal F\) is acyclic with slack \(s\) if \(\widetilde{H}_i(\bigcup_{X\in \mathcal G} X,\mathbb Q)=0\) for all nonempty \(\mathcal G\) \(\subset \mathcal F\) and all \(i\geq \max(1,s-| \mathcal G|)\)). Next, by an adaptation of a technique developed by G. Kalai and R. Meshulam in [J. Topol. 1, No. 3, 551–556 (2008; Zbl 1148.55014)], the authors prove a projection theorem which relates the Leray number of the simplicial poset \(\mathcal M(\mathcal F)\) with the Leray number \(L(\mathcal N(\mathcal F))\) of the poset \(\mathcal N(\mathcal F)\).
As \(\text{h}(\mathcal F) \leq L(\mathcal N(\mathcal F))+1\) and by using spectral sequence techniques, these two results are the main ingredients for proving the principal result of the paper (Theorem 3): If the family \(\mathcal F\) is acyclic with slack \(s\) and if any sub-family of \(\mathcal F\) of cardinality at least \(t\) intersects in at most \(r\) connected components, then \(\text{h}(\mathcal F) \leq r(\text{max}(d_{\Gamma},s,t)+1)\) where \(d_{\Gamma}\) is the smallest integer such that \(H_i(U,\mathbb Q)=0\) for every open subset \(U\) of \(\Gamma\) and every \(i\geq d_{\Gamma}\). This bound is tight. As an application, the authors get explicit bounds on Helly numbers in geometrical transversal theory. More generally, these results improve and unify various related results which are discussed in the paper.

MSC:

52A35 Helly-type theorems and geometric transversal theory
05E45 Combinatorial aspects of simplicial complexes
55T99 Spectral sequences in algebraic topology
PDFBibTeX XMLCite
Full Text: DOI arXiv HAL

References:

[1] Alon, N.; Kalai, G., Bounding the piercing number, Discrete Comput. Geom., 13, 245-256 (1995) · Zbl 0826.52006
[2] Alon, N.; Kalai, G.; Matousek, J.; Meshulam, R., Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math., 29, 1, 79-101 (2002) · Zbl 1027.52003
[3] Amenta, N., Helly-type theorems and generalized linear programming, Discrete Comput. Geom., 12, 241-261 (1994) · Zbl 0819.90056
[4] Amenta, N., A short proof of an interesting Helly-type theorem, Discrete Comput. Geom., 15, 423-427 (1996) · Zbl 0851.52007
[5] Björner, A., Posets, regular CW complexes and Bruhat order, European J. Combin., 5, 7-16 (1984) · Zbl 0538.06001
[6] Björner, A., Nerves, fibers and homotopy groups, J. Combin. Theory Ser. A, 102, 1, 88-93 (2003) · Zbl 1030.55006
[7] Borcea, C.; Goaoc, X.; Petitjean, S., Line transversals to disjoint balls, Discrete Comput. Geom., 1-3, 158-173 (2008) · Zbl 1184.52006
[8] Borsuk, K., On the imbedding of systems of compacta in simplicial complexes, Fund. Math., 35, 217-234 (1948) · Zbl 0032.12303
[9] Bott, R.; Tu, L. W., Differential Forms in Algebraic Topology, Grad. Texts in Math., vol. 82 (1982), Springer-Verlag: Springer-Verlag New York · Zbl 0496.55001
[10] Bredon, G. E., Sheaf Theory, Grad. Texts in Math., vol. 170 (1997), Springer-Verlag: Springer-Verlag New York · Zbl 0874.55001
[11] Cheong, O.; Goaoc, X.; Holmsen, A., Lower bounds to Helly numbers of line transversals to disjoint congruent balls, Israel J. Math., 190, 213-228 (2012) · Zbl 1255.52009
[12] Cheong, O.; Goaoc, X.; Holmsen, A.; Petitjean, S., Hadwiger and Helly-type theorems for disjoint unit spheres, Discrete Comput. Geom., 1-3, 194-212 (2008) · Zbl 1143.52006
[13] Cheong, O.; Goaoc, X.; Na, H.-S., Geometric permutations of disjoint unit spheres, Comput. Geom., 30, 253-270 (2005) · Zbl 1076.52002
[14] Danzer, L., Über ein Problem aus der kombinatorischen Geometrie, Arch. Math., 8, 5, 347-351 (15.XII.1957)
[15] Danzer, L.; Grünbaum, B.; Klee, V., Hellyʼs theorem and its relatives, (Klee, V., Convexity. Convexity, Proc. Sympos. Pure Math. (1963), American Mathematical Society), 101-180
[16] Debrunner, H., Helly type theorems derived from basic singular homology, Amer. Math. Monthly, 77, 375-380 (1970) · Zbl 0191.54903
[17] Helly, J. E., Radon and Carathéodory type theorems, (Gruber, P. M.; Wills, J. M., Handbook of Convex Geometry (1993), North-Holland), 389-448
[18] Eckhoff, J.; Nischke, K.-P., Morrisʼs pigeonhole principle and the Helly theorem for unions of convex sets, Bull. Lond. Math. Soc., 41, 577-588 (2009) · Zbl 1181.52011
[19] Farb, B., Group actions and Hellyʼs theorem, Adv. Math., 222, 1574-1588 (2009) · Zbl 1177.22007
[20] Friedman, G., An elementary illustrated introduction to simplicial sets, Rocky Mountain J. Math., 42, 2, 353-424 (2012) · Zbl 1248.55001
[21] Gabrielov, A.; Vorobjov, N., Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. (2), 80, 1, 35-54 (2009) · Zbl 1177.14097
[22] Godement, R., Topologie Algébrique et Théorie des Faisceaux (1973), Hermann: Hermann Paris, Troisième édition revue et corrigée, Publications de lʼInstitut de Mathématique de lʼUniversité de Strasbourg, XIII, Actualités Scientifiques et Industrielles, No. 1252 · Zbl 0275.55010
[23] Goerss, P. G.; Jardine, J. F., Simplicial Homotopy Theory, Progr. Math., vol. 174 (1999), Birkhäuser Verlag: Birkhäuser Verlag Basel · Zbl 0949.55001
[24] Goodman, J. E.; Holmsen, A.; Pollack, R.; Ranestad, K.; Sottile, F., Cremona convexity, frame convexity, and a theorem of Santaló, Adv. Geom., 6, 301-322 (2006) · Zbl 1105.52004
[25] Goodman, J. E.; Pollack, R., Foundations of a theory of convexity on affine Grassmann manifolds, Mathematika, 42, 308-328 (1995) · Zbl 0835.52002
[26] Goryunov, V.; Mond, D., Vanishing cohomology of singularities of mappings, Compos. Math., 89, 1, 45-80 (1993) · Zbl 0839.32017
[27] Greenberg, M. J., Lectures on Algebraic Topology (1967), Benjamin: Benjamin Reading, MA · Zbl 0169.54403
[28] Grünbaum, B., On common transversals, Arch. Math., 9, 465-469 (1958) · Zbl 0083.17204
[29] Grünbaum, B.; Motzkin, T. S., On components in some families of sets, Proc. Amer. Math. Soc., 12, 607-613 (1961) · Zbl 0106.01001
[30] Hatcher, A., Algebraic Topology (2002), Cambridge University Press, available at · Zbl 1044.55001
[31] Hell, S., On a topological fractional Helly theorem (2005)
[32] Hell, S., Tverberg-type theorems and the fractional Helly property (2006), Technischen Universität Berlin, PhD thesis · Zbl 1235.52002
[33] Helly, E., Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deutsch. Math.-Verein., 32, 175-176 (1923) · JFM 49.0534.02
[34] Helly, E., Über Systeme von abgeschlossenen Mengen mit gemeinschaftlichen Punkten, Monatsh. Math. Phys., 37, 281-302 (1930) · JFM 56.0499.03
[35] Holmsen, A., Recent progress on line transversals to families of translated ovals, (Goodman, J. E.; Pach, J.; Pollack, R., Computational Geometry - Twenty Years Later (2008), American Mathematical Society), 283-298 · Zbl 1148.52007
[36] Holmsen, A.; Katchalski, M.; Lewis, T., A Helly-type theorem for line transversals to disjoint unit balls, Discrete Comput. Geom., 29, 595-602 (2003) · Zbl 1030.52008
[37] Holmsen, A.; Matoušek, J., No Helly theorem for stabbing translates by lines in \(R^d\), Discrete Comput. Geom., 31, 405-410 (2004) · Zbl 1059.52011
[38] Kalai, G.; Meshulam, R., Intersections of Leray complexes and regularity of monomial ideals, J. Combin. Theory Ser. A, 113, 1586-1592 (2006) · Zbl 1105.13026
[39] Kalai, G.; Meshulam, R., Leray numbers of projections and a topological Helly-type theorem, J. Topol., 1, 551-556 (2008) · Zbl 1148.55014
[40] Kashiwara, M.; Schapira, P., Sheaves on Manifolds, Grundlehren Math. Wiss., vol. 292 (1990), Springer-Verlag: Springer-Verlag Berlin
[41] Katchalski, M., A conjecture of Grünbaum on common transversals, Math. Scand., 59, 2, 192-198 (1986) · Zbl 0618.52002
[42] Katchalski, M.; Lewis, T.; Liu, A., Geometric permutations of disjoint translates of convex sets, Discrete Math., 65, 249-259 (1987) · Zbl 0619.52002
[43] Lundell, A. T.; Weingram, S., The Topology of CW Complexes, Univ. Ser. in Higher Math. (1969), Van Nostrand Reinhold Company: Van Nostrand Reinhold Company New York · Zbl 0207.21704
[44] Matoušek, J., A Helly-type theorem for unions of convex sets, Discrete Comput. Geom., 18, 1-12 (1997) · Zbl 0889.52009
[45] Matoušek, J., Using the Borsuk-Ulam Theorem (2003), Springer-Verlag
[46] May, J. P., Simplicial Objects in Algebraic Topology, Chicago Lectures in Math. (1992), University of Chicago Press: University of Chicago Press Chicago, IL, reprint of the 1967 original · Zbl 0769.55001
[47] McCleary, J., A Userʼs Guide to Spectral Sequences, Cambridge Stud. Adv. Math., vol. 58 (2001), Cambridge University Press: Cambridge University Press Cambridge
[48] Milnor, J., The geometric realization of a semi-simplicial complex, Ann. of Math. (2), 65, 357-362 (1957) · Zbl 0078.36602
[50] Morris, H. C., Two pigeon hole principles and unions of convexly disjoint sets (1973), California Institute of Technology, PhD thesis
[51] Munkres, J. R., Elements of Algebraic Topology (1984), Addison-Wesley · Zbl 0673.55001
[52] Rourke, C. P.; Sanderson, B. J., △-sets. I. Homotopy theory, Quart. J. Math. Oxford Ser. (2), 22, 321-338 (1971) · Zbl 0226.55019
[53] Santaló, L., Un teorema sobre conjuntos de paralelepipedos de aristas paralelas, Publ. Inst. Mat. Univ. Nat. Litoral, 2, 49-60 (1940)
[54] Smale, S., A Vietoris mapping theorem for homotopy, Proc. Amer. Math. Soc., 8, 604-610 (1957) · Zbl 0089.39003
[55] Smith, J. W., On the homology structure of submersions, Math. Ann., 193, 217-224 (1971) · Zbl 0209.27801
[56] Smorodinsky, S.; Mitchell, J. S.B.; Sharir, M., Sharp bounds on geometric permutations for pairwise disjoint balls in \(R^d\), Discrete Comput. Geom., 23, 247-259 (2000) · Zbl 0946.68145
[57] Spanier, E. H., Algebraic Topology (1966), McGraw-Hill Book Co.: McGraw-Hill Book Co. New York · Zbl 0145.43303
[58] Stanley, R., \(f\)-vectors and \(h\)-vectors of simplicial posets, J. Pure Appl. Algebra, 71, 319-331 (1991) · Zbl 0727.06009
[59] Tverberg, H., Proof of Grünbaumʼs conjecture on common transversals for translates, Discrete Comput. Geom., 4, 191-203 (1989) · Zbl 0686.52008
[60] Vincensini, P., Figures convexes et variétés linéaires de lʼespace euclidien à \(n\) dimensions, Bull. Sci. Math., 59, 163-174 (1935) · Zbl 0011.41201
[61] Weibel, C. A., An Introduction to Homological Algebra, Cambridge Stud. Adv. Math., vol. 38 (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0797.18001
[62] Wenger, R., Helly-type theorems and geometric transversals, (Goodman, J. E.; OʼRourke, J., Handbook of Discrete & Computational Geometry (2004), CRC Press LLC: CRC Press LLC Boca Raton, FL), 73-96, (Chapter 4)
[63] Zhou, Y.; Suri, S., Geometric permutations of balls with bounded size disparity, Comput. Geom., 26, 3-20 (2003) · Zbl 1039.52013
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.