On topological minors in random simplicial complexes

A. Gundert, U. Wagner, Proceedings of the American Mathematical Society 144 (2016) 1815–1828.


Journal Article | Published | English

Scopus indexed
Author
Gundert, Anna; Wagner, UliIST Austria
Department
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 Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √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.
Publishing Year
Date Published
2016-04-01
Journal Title
Proceedings of the American Mathematical Society
Acknowledgement
This research was supported by the Swiss National Science Foundation (SNF Projects 200021-125309 and 200020-138230
Volume
144
Issue
4
Page
1815 - 1828
IST-REx-ID

Cite this

Gundert A, Wagner U. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 2016;144(4):1815-1828. doi:10.1090/proc/12824
Gundert, A., & Wagner, U. (2016). On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society, 144(4), 1815–1828. https://doi.org/10.1090/proc/12824
Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” Proceedings of the American Mathematical Society 144, no. 4 (2016): 1815–28. https://doi.org/10.1090/proc/12824.
A. Gundert and U. Wagner, “On topological minors in random simplicial complexes,” Proceedings of the American Mathematical Society, vol. 144, no. 4, pp. 1815–1828, 2016.
Gundert A, Wagner U. 2016. On topological minors in random simplicial complexes. Proceedings of the American Mathematical Society. 144(4), 1815–1828.
Gundert, Anna, and Uli Wagner. “On Topological Minors in Random Simplicial Complexes.” Proceedings of the American Mathematical Society, vol. 144, no. 4, American Mathematical Society, 2016, pp. 1815–28, doi:10.1090/proc/12824.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar