  An injective word over a finite alphabet $V$ is a sequence $w=v_1v_2\cdots
v_t$ of distinct elements of $V$. The set $\mathrm{inj}(V)$ of injective words
on $V$ is partially ordered by inclusion. A complex of injective words is the
order complex $\Delta(W)$ of a subposet $W \subset \mathrm{inj}(V)$. Complexes
of injective words arose recently in applications of algebraic topology to
neuroscience, and are of independent interest in topology and combinatorics. In
this article we mainly study Permutation Complexes, i.e. complexes of injective
words $\Delta(W)$, where $W$ is the downward closed subposet of
$\mathrm{inj}(V)$ generated by a set of permutations of $V$. In particular, we
determine the homotopy type of $\Delta(W)$ when $W$ is generated by two
permutations, and prove that any stable homotopy type is realizable by a
permutation complex. We describe a homotopy decomposition for the complex of
injective words $\Gamma(K)$ associated with a simplicial complex $K$, and point
out a connection to a result of Randal-Williams and Wahl. Finally, we discuss
some probabilistic aspects of random permutation complexes.
