{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:17:01Z","timestamp":1740107821039,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T00:00:00Z","timestamp":1685923200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T00:00:00Z","timestamp":1685923200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,10]]},"abstract":"Abstract<\/jats:title>Let K<\/jats:italic> be a simplicial complex on vertex set V<\/jats:italic>. K<\/jats:italic> is called d<\/jats:italic>-Leray<\/jats:italic> if the homology groups of any induced subcomplex of K<\/jats:italic> are trivial in dimensions d<\/jats:italic> and higher. K<\/jats:italic> is called d<\/jats:italic>-collapsible<\/jats:italic> if it can be reduced to the void complex by sequentially removing a simplex of size at most d<\/jats:italic> that is contained in a unique maximal face. Motivated by results of Eckhoff and of Montejano and Oliveros on \u201ctolerant\u201d versions of Helly\u2019s theorem, we define the t<\/jats:italic>-tolerance complex<\/jats:italic> of K<\/jats:italic>, $${\\mathcal {T}}_{t}(K)$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n K<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, as the simplicial complex on vertex set V<\/jats:italic> whose simplices are formed as the union of a simplex in K<\/jats:italic> and a set of size at most t<\/jats:italic>. We prove that for any d<\/jats:italic> and t<\/jats:italic> there exists a positive integer h<\/jats:italic>(t<\/jats:italic>,\u00a0d<\/jats:italic>) such that, for every d<\/jats:italic>-collapsible complex K<\/jats:italic>, the t<\/jats:italic>-tolerance complex $${\\mathcal {T}}_t(K)$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n t<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n K<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is h<\/jats:italic>(t<\/jats:italic>,\u00a0d<\/jats:italic>)-Leray. As an application, we present some new tolerant versions of the colorful Helly theorem.<\/jats:p>","DOI":"10.1007\/s00493-023-00044-5","type":"journal-article","created":{"date-parts":[[2023,6,5]],"date-time":"2023-06-05T06:01:57Z","timestamp":1685944917000},"page":"985-1006","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Leray Numbers of Tolerance Complexes"],"prefix":"10.1007","volume":"43","author":[{"given":"Minki","family":"Kim","sequence":"first","affiliation":[]},{"given":"Alan","family":"Lew","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,5]]},"reference":[{"key":"44_CR1","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/conm\/685\/13718","volume":"685","author":"N Amenta","year":"2017","unstructured":"Amenta, N., De Loera, J.A., Sober\u00f3n, P.: Helly\u2019s theorem: new variations and applications. Algebr. Geom. Methods Discrete Math. 685, 55\u201395 (2017)","journal-title":"Algebr. Geom. Methods Discrete Math."},{"issue":"2\u20133","key":"44_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(82)90115-7","volume":"40","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I.: A generalization of Carath\u00e9odory\u2019s theorem. Discrete Math. 40(2\u20133), 141\u2013152 (1982)","journal-title":"Discrete Math."},{"issue":"1","key":"44_CR3","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0097-3165(03)00015-3","volume":"102","author":"A Bj\u00f6rner","year":"2003","unstructured":"Bj\u00f6rner, A.: Nerves, fibers and homotopy groups. J. Comb. Theory Ser. A 102(1), 88\u201393 (2003)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"4","key":"44_CR4","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/0196-8858(85)90021-1","volume":"6","author":"A Bj\u00f6rner","year":"1985","unstructured":"Bj\u00f6rner, A., Korte, B., Lov\u00e1sz, L.: Homotopy properties of greedoids. Adv. Appl. Math. 6(4), 447\u2013494 (1985)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"44_CR5","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1080\/00029890.1970.11992492","volume":"77","author":"H Debrunner","year":"1970","unstructured":"Debrunner, H.: Helly type theorems derived from basic singular homology. Am. Math. Mon. 77(4), 375\u2013380 (1970)","journal-title":"Am. Math. Mon."},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"Eckhoff, J.: A survey of the Hadwiger\u2013Debrunner $$(p, q)$$-problem. In: Discrete and computational geometry. Springer. pp. 347\u2013377 (2003)","DOI":"10.1007\/978-3-642-55566-4_16"},{"issue":"18","key":"44_CR7","first-page":"1","volume":"6","author":"P Erd\u0151s","year":"1961","unstructured":"Erd\u0151s, P., Gallai, T.: On the minimal number of vertices representing the edges of a graph. Publ. Math. Inst. Hungar. Acad. Sci 6(18), 1\u2013203 (1961)","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci"},{"key":"44_CR8","first-page":"175","volume":"32","author":"E Helly","year":"1923","unstructured":"Helly, E.: \u00dcber Mengen konvexer K\u00f6rper mit gemeinschaftlichen Punkten. Jahresber. Deutsch. Math.-Verein. 32, 175\u2013176 (1923)","journal-title":"Jahresber. Deutsch. Math.-Verein."},{"key":"44_CR9","doi-asserted-by":"publisher","first-page":"P3.43","DOI":"10.37236\/9978","volume":"28","author":"AS Jobson","year":"2021","unstructured":"Jobson, A.S., K\u00e9zdy, A.E., Lehel, J.: Eckhoff\u2019s problem on convex sets in the plane. Electron. J. Comb. 28, P3.43 (2021)","journal-title":"Electron. J. Comb."},{"issue":"2","key":"44_CR10","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.aim.2004.03.009","volume":"191","author":"G Kalai","year":"2005","unstructured":"Kalai, G., Meshulam, R.: A topological colorful Helly theorem. Adv. Math. 191(2), 305\u2013311 (2005)","journal-title":"Adv. Math."},{"issue":"7","key":"44_CR11","doi-asserted-by":"publisher","first-page":"1586","DOI":"10.1016\/j.jcta.2006.01.005","volume":"113","author":"G Kalai","year":"2006","unstructured":"Kalai, G., Meshulam, R.: Intersections of Leray complexes and regularity of monomial ideals. J. Comb. Theory Ser. A 113(7), 1586\u20131592 (2006)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"44_CR12","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1112\/jtopol\/jtn010","volume":"1","author":"G Kalai","year":"2008","unstructured":"Kalai, G., Meshulam, R.: Leray numbers of projections and a topological Helly-type theorem. J. Topol. 1(3), 551\u2013556 (2008)","journal-title":"J. Topol."},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"K\u00e9zdy, A.E., Lehel, J.: An asymptotic resolution of a conjecture of Szemer\u00e9di and Petruska. (2022). arXiv:2208.11573","DOI":"10.1016\/j.disc.2023.113469"},{"key":"44_CR14","unstructured":"Khmelnitsky, I.: $$d$$-Collapsibility and its applications. Master\u2019s thesis, Technion, Haifa (2018)"},{"key":"44_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s11856-022-2308-4","volume":"249","author":"M Kim","year":"2022","unstructured":"Kim, M., Lew, A.: Complexes of graphs with bounded independence number. Israel J. Math. 249, 83\u2013120 (2022)","journal-title":"Israel J. Math."},{"key":"44_CR16","unstructured":"Lov\u00e1sz, L.: Topological methods in combinatorics. Lecture notes. (2016). http:\/\/www.cs.elte.hu\/~lovasz\/kurzusok\/topol16.pdf"},{"issue":"1","key":"44_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/s004930170006","volume":"21","author":"R Meshulam","year":"2001","unstructured":"Meshulam, R.: The clique complex and hypergraph matching. Combinatorica 21(1), 89\u201394 (2001)","journal-title":"Combinatorica"},{"issue":"2","key":"44_CR18","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s00454-010-9296-6","volume":"45","author":"L Montejano","year":"2011","unstructured":"Montejano, L., Oliveros, D.: Tolerance in Helly-type theorems. Discrete Comput. Geom. 45(2), 348\u2013357 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"44_CR19","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1023\/A:1004985022580","volume":"65","author":"D Nadler","year":"1997","unstructured":"Nadler, D.: Minimal 2-fold coverings of $${\\mathbb{E} }^d$$. Geom. Dedicata. 65(3), 305\u2013312 (1997)","journal-title":"Geom. Dedicata."},{"key":"44_CR20","first-page":"32","volume":"3","author":"M Tancer","year":"2010","unstructured":"Tancer, M.: $$d$$-Collapsibility is NP-complete for $$d\\ge 4$$. Chic. J. Theoret. Comput. Sci. 3, 32 (2010)","journal-title":"Chic. J. Theoret. Comput. Sci."},{"key":"44_CR21","doi-asserted-by":"crossref","unstructured":"Tancer, M.: Intersection patterns of convex sets via simplicial complexes: a survey. In: Thirty essays on geometric graph theory. Springer, New York. pp. 521\u2013540 (2013)","DOI":"10.1007\/978-1-4614-0110-0_28"},{"issue":"2","key":"44_CR22","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/0095-8956(85)90043-7","volume":"39","author":"Z Tuza","year":"1985","unstructured":"Tuza, Z.: Critical hypergraphs and intersecting set-pair systems. J. Comb. Theory Ser. B 39(2), 134\u2013145 (1985)","journal-title":"J. Comb. Theory Ser. B"},{"key":"44_CR23","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF01229745","volume":"26","author":"G Wegner","year":"1975","unstructured":"Wegner, G.: $$d$$-Collapsing and nerves of families of convex sets. Arch. Math. (Basel) 26, 317\u2013321 (1975)","journal-title":"Arch. Math. (Basel)"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00044-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00044-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00044-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T19:01:40Z","timestamp":1696186900000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00044-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,5]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["44"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00044-5","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2023,6,5]]},"assertion":[{"value":"7 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}