Complexes of nearly maximum diameter

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)^{-ε}) 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} \binom{n}{d}$. We also find the right first-order asymptotics for the maximum diameter of a $d$-pseudomanifold on $n$ vertices.

No reviews yet.

No comments yet.