We present several results in extremal graph and hypergraph theory of topological nature. First, we show that if α > 0 and ℓ = Ω(1αlog 1α) is an odd integer, then every graph G with n vertices and at least n1+α edges contains an ℓ-subdivision of the complete graph Kt, where t = nΘ(α). Also, this remains true if in addition the edges of G are properly colored, and one wants to find a rainbow copy of such a subdivision. In the sparser regime, we show that properly edge colored graphs on n vertices with average degree (logn)2+o(1) contain rainbow cycles, while average degree (logn)6+o(1) guarantees rainbow subdivisions of Kt for any fixed t, thus improving recent results of Janzer and Jiang et al., respectively. Furthermore, we consider certain topological notions of cycles in pure simplicial complexes (uniform hypergraphs). We show that if G is a 2-dimensional pure simplicial complex (3-graph) with n 1-dimensional and at least n1+α 2-dimensional faces, then G contains a triangulation of the cylinder and the Möbius strip with O(1αlog 1α) vertices. We present generalizations of this for higher dimensional pure simplicial complexes as well. In order to prove these results, we consider certain (properly edge colored) graphs and hypergraphs G with strong expansion. We argue that if one randomly samples the vertices (and colors) of G with not too small probability, then many pairs of vertices are connected by a short path whose vertices (and colors) are from the sampled set, with high probability.
Overlay journal.