 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 29, 2009, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Anna Gundert (FU/TU Berlin)

## An Extremal Problem for Embeddable Simplicial Complexes

It is easy to prove that any $k$-dimensional simplicial complex embeds into $\R^{2k+1}$, so the maximal number of $k$-simplices one can get when embedding into $\R^{2k+1}$ is ${n \choose {k+1}} = \Theta(n^{k+1})$ where $n$ is the number of vertices.

For the case $k=2$ this yields $\Theta(n^3)$ for embeddability into $\R^5$. One can also show that a 2-complex which embeds into $\R^3$ can have at most $n(n-3) = \Theta(n^2)$ triangles. What happens in $\R^4$ is an open question.

This talk will address the general question of the maximal number of $k$-simplices for a complex which is embeddable into $\R^{d}$ for some $k \leq d \leq 2k$. A lower bound of $f_k(C_{d+ 1}(n)) = \Omega(n^{\lceil\frac{d}{2}\rceil})$, which might even be sharp, is given by the cyclic polytopes. To find upper bounds for the cases $d=2k$ we look for forbidden subcomplexes. A generalization of the theorem of van Kampen and Flores yields those. Then the problem can be tackled with the methods of extremal hypergraph theory, which gives an upper bound of $O(n^{d+1-\frac{1}{3^d}})$.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks