Topological connectivity of random permutation complexes

Abstract

Let ${\mathbb{S}}_n$ denote the symmetric group on $[n]=\{1,\dots ,n\}$ with the uniform probability measure. For a permutation $\pi \in {\mathbb{S}}_n$ let $X_{\pi }$ denote the simplicial complex on the vertex set $[n]$ whose simplices are all $\{i_0,\dots ,i_m\}\subset [n]$ such that $i_0<\cdots <i_m$ and $\pi (i_0)<\cdots <\pi (i_m)$. For $r\ge 0$ let $p_r(n)$ denote the probability that $X_{\pi }$ is not topologically $r$-connected for $\pi \in {\mathbb{S}}_n$. It is shown that for fixed $r\ge 0$ there exist constants $0<C_r,C_r^{\prime }<\infty$ such that \[ C_r \frac{(\log n)^r}{n} \leq p_r(n) \leq C_r' \frac{(\log n)^{2r}}{n}. \]

12 pages, 2 figures