Minors in random and expanding hypergraphs

U. Wagner, in:, ACM, 2011, pp. 351–360.

No fulltext has been uploaded. References only!

Conference Paper | Published
We introduce a new notion of minors for simplicial complexes (hypergraphs), so-called homological minors. Our motivation is to propose a general approach to attack certain extremal problems for sparse simplicial complexes and the corresponding threshold problems for random complexes. In this paper, we focus on threshold problems. The basic model for random complexes is the Linial-Meshulam model Xk(n, p). By definition, such a complex has n vertices, a complete (k -1)-dimensional skeleton, and every possible k-dimensional simplex is chosen independently with probability p. We show that for every k, t≥ 1, there is a constant C = C(k, t) such that for p≥ C/n, the random complex Xk(n, p) asymptotically almost surely contains K tk (the complete k-dimensional complex on t vertices) as a homological minor. As corollary, the threshold for (topological) embeddability of Xk(n, p) into R2k is at p = θ(1/n). The method can be extended to other models of random complexes (for which the lower skeleta are not necessarily complete) and also to more general Tverberg-type problems, where instead of continuous maps without doubly covered image points (embeddings), we consider maps without qfold covered image points.
Publishing Year
Date Published
351 - 360
SGC: Symposuim on Computational Geometry

Cite this

Wagner U. Minors in random and expanding hypergraphs. In: ACM; 2011:351-360. doi:10.1145/1998196.1998256
Wagner, U. (2011). Minors in random and expanding hypergraphs (pp. 351–360). Presented at the SGC: Symposuim on Computational Geometry, ACM. https://doi.org/10.1145/1998196.1998256
Wagner, Uli. “Minors in Random and Expanding Hypergraphs,” 351–60. ACM, 2011. https://doi.org/10.1145/1998196.1998256.
U. Wagner, “Minors in random and expanding hypergraphs,” presented at the SGC: Symposuim on Computational Geometry, 2011, pp. 351–360.
Wagner U. 2011. Minors in random and expanding hypergraphs. SGC: Symposuim on Computational Geometry, 351–360.
Wagner, Uli. Minors in Random and Expanding Hypergraphs. ACM, 2011, pp. 351–60, doi:10.1145/1998196.1998256.


Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar