Nerves, minors, and piercing numbers
HTML articles powered by AMS MathViewer
- by Andreas F. Holmsen, Minki Kim and Seunghun Lee PDF
- Trans. Amer. Math. Soc. 371 (2019), 8755-8779 Request permission
Abstract:
We make the first step towards a “nerve theorem” for graphs. Let $G$ be a simple graph and let $\mathcal {F}$ be a family of induced subgraphs of $G$ such that the intersection of any members of $\mathcal {F}$ is either empty or connected. We show that if the nerve complex of $\mathcal {F}$ has non-vanishing homology in dimension three, then $G$ contains the complete graph on five vertices as a minor. As a consequence we confirm a conjecture of Goaoc concerning an extension of the planar $(p,q)$ theorem due to Alon and Kleitman: Let $\mathcal {F}$ be a finite family of open connected sets in the plane such that the intersection of any members of $\mathcal {F}$ is either empty or connected. If among any $p \geq 3$ members of $\mathcal {F}$ there are some three that intersect, then there is a set of $C$ points which intersects every member of $\mathcal {F}$, where $C$ is a constant depending only on $p$.References
- Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman, Point selections and weak $\epsilon$-nets for convex hulls, Combin. Probab. Comput. 1 (1992), no. 3, 189–200. MR 1208800, DOI 10.1017/S0963548300000225
- N. Alon and G. Kalai, Bounding the piercing number, Discrete Comput. Geom. 13 (1995), no. 3-4, 245–256. MR 1318775, DOI 10.1007/BF02574042
- Noga Alon, Gil Kalai, Jiří Matoušek, and Roy Meshulam, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math. 29 (2002), no. 1, 79–101. MR 1921545, DOI 10.1016/S0196-8858(02)00003-9
- Noga Alon and Daniel J. Kleitman, Piercing convex sets and the Hadwiger-Debrunner $(p,q)$-problem, Adv. Math. 96 (1992), no. 1, 103–112. MR 1185788, DOI 10.1016/0001-8708(92)90052-M
- Imre Bárány, A generalization of Carathéodory’s theorem, Discrete Math. 40 (1982), no. 2-3, 141–152. MR 676720, DOI 10.1016/0012-365X(82)90115-7
- Imre Bárány and Jiří Matoušek, A fractional Helly theorem for convex lattice sets, Adv. Math. 174 (2003), no. 2, 227–235. MR 1963693, DOI 10.1016/S0001-8708(02)00037-3
- A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872. MR 1373690
- Anders Björner, Nerves, fibers and homotopy groups, J. Combin. Theory Ser. A 102 (2003), no. 1, 88–93. MR 1970978, DOI 10.1016/S0097-3165(03)00015-3
- Karol Borsuk, On the imbedding of systems of compacta in simplicial complexes, Fund. Math. 35 (1948), 217–234. MR 28019, DOI 10.4064/fm-35-1-217-234
- Éric Colin de Verdière, Grégory Ginot, and Xavier Goaoc, Helly numbers of acyclic families, Adv. Math. 253 (2014), 163–193. MR 3148550, DOI 10.1016/j.aim.2013.11.004
- Reinhard Diestel, Graph theory, 5th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. MR 3644391, DOI 10.1007/978-3-662-53622-3
- Jürgen Eckhoff, Helly, Radon, and Carathéodory type theorems, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 389–448. MR 1242986
- Jürgen Eckhoff, An upper-bound theorem for families of convex sets, Geom. Dedicata 19 (1985), no. 2, 217–227. MR 809468, DOI 10.1007/BF00181472
- Jack Edmonds, Monique Laurent, and Alexander Schrijver, A minor-monotone graph parameter based on oriented matroids, Discrete Math. 165/166 (1997), 219–226. Graphs and combinatorics (Marseille, 1995). MR 1439272, DOI 10.1016/S0012-365X(96)00172-0
- Paul Erdős and Miklós Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), no. 2, 181–192. MR 726456, DOI 10.1007/BF02579292
- István Fáry, On straight line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233. MR 26311
- Xavier Goaoc, Pavel Paták, Zuzana Patáková, Martin Tancer, and Uli Wagner, Bounding Helly numbers via Betti numbers, A journey through discrete mathematics, Springer, Cham, 2017, pp. 407–447. MR 3726608
- Dejan Govc and Primoz Skraba, An approximate nerve theorem, Found. Comput. Math. 18 (2018), no. 5, 1245–1297. MR 3857910, DOI 10.1007/s10208-017-9368-6
- H. Hadwiger and H. Debrunner, Über eine Variante zum Hellyschen Satz, Arch. Math. (Basel) 8 (1957), 309–313 (German). MR 92987, DOI 10.1007/BF01898794
- S. Hell, On a topological fractional Helly theorem, arXiv:math/0506399, 2005.
- E. Helly, Über Mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deutsch. Math.-Verein. 32 (1923), 175–176.
- Rephael Wenger, Helly-type theorems and geometric transversals, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 63–82. MR 1730160
- Hein van der Holst, Monique Laurent, and Alexander Schrijver, On a minor-monotone graph invariant, J. Combin. Theory Ser. B 65 (1995), no. 2, 291–304. MR 1358991, DOI 10.1006/jctb.1995.1056
- Gil Kalai, Intersection patterns of convex sets, Israel J. Math. 48 (1984), no. 2-3, 161–174. MR 770699, DOI 10.1007/BF02761162
- Gil Kalai, Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999) Adv. Stud. Pure Math., vol. 33, Math. Soc. Japan, Tokyo, 2002, pp. 121–163. MR 1890098, DOI 10.2969/aspm/03310121
- Gil Kalai and Roy Meshulam, A topological colorful Helly theorem, Adv. Math. 191 (2005), no. 2, 305–311. MR 2103215, DOI 10.1016/j.aim.2004.03.009
- Gil Kalai and Roy Meshulam, Leray numbers of projections and a topological Helly-type theorem, J. Topol. 1 (2008), no. 3, 551–556. MR 2417442, DOI 10.1112/jtopol/jtn010
- M. Katchalski and A. Liu, A problem of geometry in $\textbf {R}^{n}$, Proc. Amer. Math. Soc. 75 (1979), no. 2, 284–288. MR 532152, DOI 10.1090/S0002-9939-1979-0532152-6
- Minki Kim, A note on the colorful fractional Helly theorem, Discrete Math. 340 (2017), no. 1, 3167–3170. MR 3557813, DOI 10.1016/j.disc.2016.07.001
- Daniel J. Kleitman, András Gyárfás, and Géza Tóth, Convex sets in the plane with three of every four meeting, Combinatorica 21 (2001), no. 2, 221–232. Paul Erdős and his mathematics (Budapest, 1999). MR 1832447, DOI 10.1007/s004930100020
- Roy Meshulam, The clique complex and hypergraph matching, Combinatorica 21 (2001), no. 1, 89–94. MR 1805715, DOI 10.1007/s004930170006
- Bojan Mohar, What is $\dots$ a graph minor, Notices Amer. Math. Soc. 53 (2006), no. 3, 338–339. MR 2208386
- Luis Montejano, A variation on the homological nerve theorem, Topology Appl. 225 (2017), 139–144. MR 3649877, DOI 10.1016/j.topol.2017.04.029
- Neil Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004), no. 2, 325–357. MR 2099147, DOI 10.1016/j.jctb.2004.08.001
- Alexander Schrijver, Minor-monotone graph invariants, Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 163–196. MR 1477747, DOI 10.1017/CBO9780511662119.007
- P. Soberón, Helly-type theorems for the diameter, Bull. Lond. Math. Soc. 48 (2016), no. 4, 577–588. MR 3532134, DOI 10.1112/blms/bdw027
- Martin Tancer, Intersection patterns of convex sets via simplicial complexes: a survey, Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 521–540. MR 3205172, DOI 10.1007/978-1-4614-0110-0_{2}8
- K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), no. 1, 570–590 (German). MR 1513158, DOI 10.1007/BF01594196
Additional Information
- Andreas F. Holmsen
- Affiliation: Department of Mathematical Sciences, KAIST, Daejeon 34141, South Korea
- MR Author ID: 685253
- Email: andreash@kaist.edu
- Minki Kim
- Affiliation: Department of Mathematical Sciences, KAIST, Daejeon 34141, South Korea
- Address at time of publication: Department of Mathematics, Technion, Haifa, Israel
- MR Author ID: 1183004
- Email: kmk90@kaist.ac.kr
- Seunghun Lee
- Affiliation: Department of Mathematical Sciences, KAIST, Daejeon 34141, South Korea
- MR Author ID: 1170640
- Email: prosolver@kaist.ac.kr
- Received by editor(s): June 16, 2017
- Received by editor(s) in revised form: February 20, 2018
- Published electronically: March 19, 2019
- Additional Notes: All authors were supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03930998).
The first author was also partially supported by Swiss National Science Foundation grants 200020-165977 and 200021-162884.
The second author was partially supported at the Technion by ISF grant no. 2023464 and BSF grant no. 2006099
Minki Kim is the corresponding author - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 8755-8779
- MSC (2010): Primary 05C10, 05C83, 52A35
- DOI: https://doi.org/10.1090/tran/7608
- MathSciNet review: 3955563