On the Subdivision Containment Problem for Random 2-Complexes
Anna GundertUli Wagner · 2013
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 a copy of a subdivision of the given graph, it is wellknown that the (sharp) threshold is at p = 1=n. We consider the analogous question for random 2dimensional complexes X 2 (n;p). Improving previous results, we show that p = (1 = p n) is the (coarse) threshold for containing a subdivision of any xed complete 2-complex.