On topological minors in random simplicial complexes
HTML articles powered by AMS MathViewer
- by Anna Gundert and Uli Wagner PDF
- Proc. Amer. Math. Soc. 144 (2016), 1815-1828 Request permission
Abstract:
For random graphs, the containment problem considers the probability that a binomial random graph $G(n,p)$ contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at $p=1/n$. We consider a natural analogue of this question for higher-dimensional random complexes $X^k(n,p)$, first studied by Cohen, Costa, Farber and Kappeler for $k=2$.
Improving previous results, we show that $p=\Theta (1/\sqrt {n})$ is the (coarse) threshold for containing a subdivision of any fixed complete $2$-complex. For higher dimensions $k>2$, we get that $p=O(n^{-1/k})$ is an upper bound for the threshold probability of containing a subdivision of a fixed $k$-dimensional complex.
References
- Miklós Ajtai, János Komlós, and Endre Szemerédi, Topological complete subgraphs in random graphs, Studia Sci. Math. Hungar. 14 (1979), no. 1-3, 293–297 (1982). MR 645536
- Sylwia Antoniuk, Tomasz Łuczak, and Jacek Świątkowski, Collapse of random triangular groups: a closer look, Bull. Lond. Math. Soc. 46 (2014), no. 4, 761–764. MR 3239613, DOI 10.1112/blms/bdu034
- Lior Aronshtam, Nathan Linial, Tomasz Łuczak, and Roy Meshulam, Collapsibility and vanishing of top homology in random simplicial complexes, Discrete Comput. Geom. 49 (2013), no. 2, 317–334. MR 3017914, DOI 10.1007/s00454-012-9483-8
- Eric Babson, Christopher Hoffman, and Matthew Kahle, The fundamental group of random 2-complexes, J. Amer. Math. Soc. 24 (2011), no. 1, 1–28. MR 2726597, DOI 10.1090/S0894-0347-2010-00677-7
- Edward A. Bender and E. Rodney Canfield, The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A 43 (1986), no. 2, 244–257. MR 867650, DOI 10.1016/0097-3165(86)90065-8
- E. A. Bender, E. R. Canfield, and R. W. Robinson, The enumeration of maps on the torus and the projective plane, Canad. Math. Bull. 31 (1988), no. 3, 257–271. MR 956356, DOI 10.4153/CMB-1988-039-4
- Edward A. Bender and L. Bruce Richmond, A survey of the asymptotic behaviour of maps, J. Combin. Theory Ser. B 40 (1986), no. 3, 297–329. MR 842997, DOI 10.1016/0095-8956(86)90086-9
- Béla Bollobás, Random graphs, Combinatorics (Swansea, 1981) London Math. Soc. Lecture Note Ser., vol. 52, Cambridge Univ. Press, Cambridge-New York, 1981, pp. 80–102. MR 633650
- B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI 10.1007/BF02579198
- W. G. Brown, P. Erdős, and V. T. Sós, Some extremal problems on $r$-graphs, New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971) Academic Press, New York, 1973, pp. 53–63. MR 0351888
- D. Cohen, A. Costa, M. Farber, and T. Kappeler, Topology of random 2-complexes, Discrete Comput. Geom. 47 (2012), no. 1, 117–149. MR 2886093, DOI 10.1007/s00454-011-9378-0
- P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
- Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-sat problem, J. Amer. Math. Soc. 12 (1999), no. 4, 1017–1054. With an appendix by Jean Bourgain. MR 1678031, DOI 10.1090/S0894-0347-99-00305-7
- Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993–3002. MR 1371123, DOI 10.1090/S0002-9939-96-03732-X
- Zhicheng Gao, The number of rooted triangular maps on a surface, J. Combin. Theory Ser. B 52 (1991), no. 2, 236–249. MR 1110472, DOI 10.1016/0095-8956(91)90065-R
- Anna Gundert and Uli Wagner, On the subdivision containment problem for random 2-complexes, Young Researchers Forum - SoCG 2013.
- Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
- John Philip Huneke, A minimum-vertex triangulation, J. Combin. Theory Ser. B 24 (1978), no. 3, 258–266. MR 0480137, DOI 10.1016/0095-8956(78)90043-6
- S. Janson, On concentration of probability, Contemporary combinatorics, Bolyai Soc. Math. Stud., vol. 10, János Bolyai Math. Soc., Budapest, 2002, pp. 289–301. MR 1919574
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- Gil Kalai, Many triangulated spheres, Discrete Comput. Geom. 3 (1988), no. 1, 1–14. MR 918176, DOI 10.1007/BF02187893
- D. Korándi, Y. Peled, and B. Sudakov, A random triadic process, Preprint, arXiv:1503.05072, 2015.
- Dmitry N. Kozlov, The threshold function for vanishing of the top homology group of random $d$-complexes, Proc. Amer. Math. Soc. 138 (2010), no. 12, 4517–4527. MR 2680076, DOI 10.1090/S0002-9939-2010-10596-8
- Michael Krivelevich and Benny Sudakov, The phase transition in random graphs: a simple proof, Random Structures Algorithms 43 (2013), no. 2, 131–138. MR 3085765, DOI 10.1002/rsa.20470
- Nathan Linial and Roy Meshulam, Homological connectivity of random 2-complexes, Combinatorica 26 (2006), no. 4, 475–487. MR 2260850, DOI 10.1007/s00493-006-0027-9
- Jiří Matoušek, Using the Borsuk-Ulam theorem, Universitext, Springer-Verlag, Berlin, 2003. Lectures on topological methods in combinatorics and geometry; Written in cooperation with Anders Björner and Günter M. Ziegler. MR 1988723
- R. Meshulam and N. Wallach, Homological connectivity of random $k$-dimensional complexes, Random Structures Algorithms 34 (2009), no. 3, 408–417. MR 2504405, DOI 10.1002/rsa.20238
- Julian Pfeifle and Günter M. Ziegler, Many triangulated 3-spheres, Math. Ann. 330 (2004), no. 4, 829–837. MR 2102314, DOI 10.1007/s00208-004-0594-2
- Edwin H. Spanier, Algebraic topology, Springer-Verlag, New York-Berlin, 1981. Corrected reprint. MR 666554
- W. T. Tutte, A census of planar maps, Canadian J. Math. 15 (1963), 249–271. MR 146823, DOI 10.4153/CJM-1963-029-x
- W. T. Tutte, On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 (1968), 64–74. MR 218276, DOI 10.1090/S0002-9904-1968-11877-4
- W. T. Tutte, The enumerative theory of planar maps, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 437–448. MR 0364004
Additional Information
- Anna Gundert
- Affiliation: Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50923 Köln, Germany
- MR Author ID: 1024036
- Email: anna.gundert@uni-koeln.de
- Uli Wagner
- Affiliation: IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria
- MR Author ID: 672933
- Email: uli@ist.ac.at
- Received by editor(s): April 16, 2014
- Received by editor(s) in revised form: April 30, 2015, and May 4, 2015
- Published electronically: September 24, 2015
- Additional Notes: This research was supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230). Work on this paper by the first author was conducted at the Institute of Theoretical Computer Science, ETH Zürich.
- Communicated by: Patricia L. Hersh
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 144 (2016), 1815-1828
- MSC (2010): Primary 55U10; Secondary 05C80, 60D05
- DOI: https://doi.org/10.1090/proc/12824
- MathSciNet review: 3451256