Complexes of nearly maximum diameter

Abstract

The diameter of a strongly connected $d$-dimensional simplicial complex is the diameter of its dual graph. We provide a probabilistic proof of the existence of $d$-dimensional simplicial complexes with diameter $(\frac{1}{d\cdot d!}-(\log n{)}^{-\epsilon })n^d$. Up to the first order term, this is the best possible lower bound for the maximum diameter of a $d$-complex on $n$ vertices as a simple volume argument shows that the diameter of a $d$-dimensional simplicial complex is at most $\frac{1}{d}\left(\genfrac{}{}{0ex}{}{n}{d}\right)$. We also find the right first-order asymptotics for the maximum diameter of a $d$-pseudomanifold on $n$ vertices.

19 pages