Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



On topological minors in random simplicial complexes

Authors: Anna Gundert and Uli Wagner
Journal: Proc. Amer. Math. Soc. 144 (2016), 1815-1828
MSC (2010): Primary 55U10; Secondary 05C80, 60D05
Published electronically: September 24, 2015
MathSciNet review: 3451256
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 55U10, 05C80, 60D05

Retrieve articles in all journals with MSC (2010): 55U10, 05C80, 60D05

Additional Information

Anna Gundert
Affiliation: Mathematisches Institut, Universität zu Köln, Weyertal 86–90, 50923 Köln, Germany

Uli Wagner
Affiliation: IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria

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
Article copyright: © Copyright 2015 American Mathematical Society