On the topology of complexes of injective words

Ran Levi; Roy Meshulam; Wojtek Chacholski

REVIEW 1 major objections 5 minor 14 references

On the topology of complexes of injective words

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every stable homotopy type is a permutation complex

desk verdict New stable realizability and two-permutation classification, with a useful decomposition formula; the one load-bearing lemma that looks fragile actually checks out, and the only fixes are conventions. read the letter →

arxiv 1908.03394 v1 pith:SMV563UI submitted 2019-08-09 math.AT

Wojtek Chacholski , Ran Levi , Roy Meshulam This is my paper · ORCID

classification math.AT MSC 55P1505E4555U10

keywords injectivewordspermutationcomplexesstablehomotopytypesorderdimensionsuspensionderangementsrandompermutations

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that stable homotopy types are not exotic: for every finite simplicial complex $Y$, there are positive $r,n,m$ and permutations $\sigma_1,\dots,\sigma_m$ of $n$ symbols such that the iterated suspension $\Sigma^r Y$ is homotopy equivalent to a permutation complex—a space built purely from ordered words of distinct symbols. The construction is explicit and uses the order dimension of the face poset of $Y$ to choose the permutations; the resulting complex is exactly $\Sigma^{2d-1}Y$ for $d$ equal to that dimension. If the result is right, every stable shape that appears in algebraic topology can be encoded by a finite collection of permutations, giving an unexpected combinatorial universality. The paper also classifies the two-permutation case (wedges of spheres), decomposes the complex of injective words of a connected complex into suspensions of its links, and derives asymptotics for random permutation complexes.

What carries the argument

The load-bearing object is the intersection poset $Q(\sigma_1,\dots,\sigma_m)$: its order complex is exactly the intersection of the individual complexes $X(\sigma_i)$. The corresponding identity for unions is Lemma 2.3: if $d$ complexes have all proper intersections contractible, their union is homotopy equivalent to the $(d-1)$-fold suspension of the total intersection. The construction's hinge is a combinatorial fact about the transpositions $\eta_k$ that swap $2k-1$ and $2k$: any proper subfamily of the posets $Q(\eta_i:i\in I)$ has contractible order complex, while the full family is a sphere $S^{d-1}$. Concatenating these transpositions with linear orders that encode the face poset of $Y$ forces every proper intersection to be contractible and the total intersection to be $\Sigma^dY$, so Lemma 2.3 delivers the desired suspension.

What would settle it

A direct check of that fact would settle the construction: compute the order complex of $Q(\eta_i:i\in I)$ for a fixed $d\ge 4$ and every nonempty proper subset $I$ of the transposition pairs; any non-contractible outcome would invalidate the proof of Theorem 2.5.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Theorem 2.5: if $Y$ is a finite simplicial complex whose face poset has $n$ elements and order dimension $d$, then there are permutations $\sigma_1,\dots,\sigma_d$ of $n+2d$ symbols with $X(\sigma_1,\dots,\sigma_d)\simeq \Sigma^{2d-1}Y$. In other words, every finite complex becomes, after enough suspensions, a permutation complex. The proof constructs each $\sigma_k$ by concatenating a linear order that encodes the face poset with a transposition of a fresh pair of symbols; proper intersections of the individual complexes are contractible, the total intersection is homotopy equivalent to $\Sigma^d Y$, and Lemma 2.3 converts the union into the iterated suspension. A second main result decomposes $\Gamma(K)$, the complex of injective words on a connected complex $K$, as a wedge of suspensions of links: $\Gamma(K)\simeq \bigvee_{\sigma\in K}\bigvee_{D(|\sigma|)}\Sigma^{|\sigma|}\operatorname{lk}(K,\sigma)$, where $D(|\sigma|)$ is the number of derangements of a set of size $|\sigma|$ and a wedge means gluing the pieces at one common point.

Load-bearing premise

The construction rests on one combinatorial contractibility fact about the transposition posets: for every nonempty proper subset $I$ of the chosen transpositions, the order complex of $Q(\eta_i:i\in I)$ is contractible, and if that fact failed the union would not collapse to the required iterated suspension.

Editorial extensions

If this is right

Every finite stable homotopy type has a finite, purely combinatorial representative: a finite list of permutations, with no geometric data beyond the ordering of symbols.
The suspension degree needed for a complex $Y$ is at most $2\dim(P(Y))-1$, so complexes whose face posets have small order dimension are realized by small permutation complexes.
For two permutations, every permutation complex is either contractible or a wedge of spheres of dimension at least $1$, and every finite wedge of spheres $S^{k_1}\vee\dots\vee S^{k_m}$ occurs.
For a connected complex $K$, the homology of $\Gamma(K)$ is the sum, over faces $\sigma$, of the homology of the link $\operatorname{lk}(K,\sigma)$ shifted by $|\sigma|$, with multiplicity the derangement number $D(|\sigma|)$.
For random two-permutation complexes, the expected reduced Euler characteristic has absolute value $O(n^{-1/4})$, matching the intuition that odd and even spheres appear in nearly equal numbers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the construction encodes the face poset by linear orders, the minimal suspension needed for a given complex is plausibly controlled by the order dimension of its face poset; one could test whether the $2d-1$ bound can be lowered for specific families such as spheres or projective planes.
The same encoding by permutations may extend beyond simplicial complexes: any finite regular CW complex has a face poset, and the construction suggests its stable homotopy type is also realizable by a permutation complex.
The 15-permutation example in $S_4$ realizing $\Sigma\mathbb{RP}^2$ that the authors mention suggests the general suspension bound is far from optimal; one might conjecture that every finite complex $Y$ admits a stable realization with suspension bounded linearly in the dimension of $Y$, rather than in the size of its face poset.
The near-zero expected Euler characteristic for two random permutations is a statistical hint, not a proof, that odd and even dimensional spheres balance in large random permutation complexes; direct simulation of $X_{2,n}$ for moderate $n$ could test whether the balance holds for homology rather than only for Euler characteristic.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear Colleague,

Read the Chacholski–Levi–Meshulam paper. The thing to know: the stable realization theorem (every finite complex shows up as a suspension of a permutation complex) and the two-permutation wedge classification are genuinely new, and the Γ(K) decomposition is a useful general formula. The point the reader flagged as load-bearing, Eq. (12), actually holds — for a proper family of transpositions the poset is a total order, so contractible. The paper is sound; the only real fixes are conventions.

The proofs are mostly standard poset-topology ingredients, but the packaging and results are worth it. Theorem 2.5 gives an explicit construction using order dimension and transposition blocks; the induction in Lemma 2.3 is clean. Theorem 3.4 reduces pairs of permutations to intersection triples and alternating sequences, and shows exactly which wedges of spheres occur. That's a satisfying answer. As a bonus, Theorem 1.8 gives a short proof of the Randal-Williams–Wahl connectivity bound, which suggests the decomposition is the right way to see that result.

Soft spots, in order of real softness. First, the wedge in Theorem 1.8 must include the empty face with D(0)=1 and lk(K,∅)=K; without that convention the K summand that the proof actually produces is missing from the statement. Second, Theorem 2.5 states 'any finite simplicial complex Y' but the proof only covers the nonempty case (P(Y) ≠ ∅); the empty case is trivial but should be said. Neither affects the substantive claims. The flagged Eq. (12) is not a gap, though it is the place to check if the construction is going to break.

Citations are appropriate. [12] is Levi's own neuroscience paper used only as motivation; the core results are cited to Farmer, Björner–Wachs, Björner–Wachs–Welker, Brown, and Szegő. No citation-pattern problem.

This paper is for combinatorial topologists and people working with order complexes of injective words. It deserves serious peer review. I would accept it with minor revision: state the empty-face convention in Theorem 1.8, and add a line on the empty complex in Theorem 2.5.

Referee Report

1 major / 5 minor

Summary. The paper studies complexes of injective words, focusing on permutation complexes, which are order complexes of subposets of injective words generated by one or more permutations. The main results are: (1) Theorem 1.5/2.5, stating that every finite simplicial complex, after a sufficiently high suspension, is homotopy equivalent to a permutation complex; (2) Theorem 1.6/3.4, classifying complexes generated by two permutations as wedges of spheres and showing that every finite wedge of spheres can be so realized; (3) Theorem 1.8, an explicit homotopy decomposition of the complex of injective words Γ(K) associated to a simplicial complex K, with an application to a connectivity result of Randal-Williams and Wahl; and (4) probabilistic results for random permutation complexes, including an asymptotic estimate for the expected reduced Euler characteristic and a bound for the expected homological dimension. The proofs use standard tools: order complexes, the Björner-Wachs-Welker poset fiber theorem, Dushnik-Miller order dimension, the nerve lemma, and an induction on permutation pairs.

Significance. If the results are correct, the stable realization theorem is a striking flexibility result: a very restricted class of complexes of injective words is shown to realize all stable homotopy types, with an explicit suspension bound in terms of the order dimension of the face poset. The two-permutation classification is clean and complete, and the Γ(K) decomposition is elegant and gives a short proof of a previously known connectivity statement. The paper is well organized, gives detailed proofs, and properly credits the external results on which it builds. The probabilistic sections are secondary but provide useful quantitative information about random permutation complexes.

major comments (1)

[§2, Theorem 2.5 and Eq. (13)] The proof of Theorem 2.5 fails when d=1, which occurs in particular when Y is a single point. The equality Δ(Q(η_1,...,η_d)) ≃ S^{d-1} in Eq. (13) is false for d=1: the poset Q(η_1) is a two-element chain, whose order complex is an edge and hence contractible, not a 0-sphere. Consequently the construction in the proof gives X(σ_1) contractible, not Σ^{1}Y ≃ S^1 as claimed, so Theorem 2.5 is false as stated for Y a point. The empty complex is also not covered, since d=0 makes Σ^{2d-1}Y undefined. This is load-bearing because Theorem 2.5 is the detailed form of the headline Theorem 1.5, which is stated for every finite simplicial complex. I recommend restricting Theorem 2.5 to nonempty Y with at least two nonempty faces, or handling Y a point separately (for instance via the two-permutation realization of S^1 from Theorem 3.4(b)), and explicitly excluding the empty complex; the stable realizability claim for all nonempty complexes remains intact after such a patch.

minor comments (5)

[§1, Theorem 1.5] The word "premutations" in the statement of Theorem 1.5 is a typo and should read "permutations".
[§4, proof of Theorem 1.8] The sentence "Therefore Δ(f^{-1}(P(K)_{<σ})) is (|σ|-2)-connected" should refer to Δ(f^{-1}(P(K)_{≤σ})) instead of the strict lower fiber. The lower fiber need not be (|σ|-2)-connected: for a 2-simplex σ it is the disjoint union of two vertices. What is needed for the Björner-Wachs-Welker theorem is the connectivity of the ≤-fiber, and that is what was established in the previous sentence.
[§4, Eq. (26)] In the displayed decomposition following Eq. (26), the index "∅≠σ∈X" contains a typo: it should be "∅≠σ∈K".
[§1, Theorem 1.8 and §4, Corollary 4.2] The wedge in formula (2) is over all σ∈K including the empty simplex, which requires conventions D(0)=1, lk(K,∅)=K, and Σ^0K=K. These conventions are not stated explicitly; the proof separately derives K ∨ (wedge over nonempty σ). Adding a sentence clarifying these conventions would prevent confusion.
[§5, Eq. (3)] The k=0 term in formula (3) involves (-1)^{-1}, which is formally acceptable but unconventional. For readability, consider writing the sum from k=1 and adding the k=0 contribution -1 explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central stable-realization result and the Gamma(K) decomposition are derived from independent lemmas and external results; the only self-citation is motivational and not load-bearing.

full rationale

I walked the derivation chain of the main theorems. Theorem 2.5 constructs permutations from a realizer of the face poset P(Y) and computes all intersections via Lemma 2.2 and the join identity (6). The pivotal contractibility claim (12) is not assumed but follows: for a nonempty proper subset I of the transpositions and j not in I, the elements 2j-1 and 2j are comparable with every element of Q(eta_i : i in I), so that order complex is a cone and hence contractible. The full intersection is Y * S^{d-1} by (13)-(14), and Lemma 2.3 then yields the iterated suspension in (10). No fitted parameter is relabelled as a prediction, and no result is imported from the authors' own prior work. The proof of Theorem 1.8 uses the external Bjorner-Wachs-Welker poset fiber theorem and the external Bjorner-Wachs description of Delta(Inj([n])); the fibers are computed directly from the definition of M(K). Theorem 1.6 is proved from the decomposition (15) and an induction with Mayer-Vietoris, and Proposition 1.10 uses Farmer's chain complex and an external Laguerre asymptotics bound. The only author-overlapping citation, [12], appears in the introduction as motivation ('This paper arose from considering the possible homotopy types of these directed flag complexes') and is not an input to any theorem. I therefore find no circular step and set the score to 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces new definitions (permutation complexes, intersection triples, alternating sequences) but these are constructions, not postulated entities with hidden evidence burdens. The central proofs rely on established external theorems listed above, plus lemmas proved inside the paper. No free parameters are fitted to data.

assumptions (6)

standard math Farmer's theorem: the homology of X(w_1,...,w_m) is the homology of the chain complex generated by words in W(w_1,...,w_m) (Theorem 1.3 of [6]).
Used in Section 5 to derive the expectation formula for reduced Euler characteristic and implicitly in the Γ(K) computation.
standard math Björner-Wachs: ∆(Inj([n])) is homotopy equivalent to a wedge of D(n) copies of S^{n-1} (Theorem 1.2 of [3]).
Identifies the fibers f^{-1}(P(K)_{≤σ}) in the proof of Theorem 1.8.
standard math Björner-Wachs-Welker poset fiber theorem (Theorem 4.1 of [4]).
The black-box decomposition theorem used to derive the Γ(K) wedge formula; the connectedness hypotheses are checked in the proof.
standard math Dushnik-Miller and Hiraguchi bounds on order dimension: dim(P) ≤ |P| and dim(P) ≤ floor(|P|/2) for |P|≥4.
Guarantees the existence of d permutations representing the face poset P(Y) in Theorem 2.5.
standard math Szego's asymptotic |L_n(1)| = O(n^{-1/4}) for Laguerre polynomials.
Used in Proposition 1.10(b) to bound the expected reduced Euler characteristic.
standard math Nerve lemma and the standard gluing theorem (Brown, Corollary 7.4.3) underlying Lemma 2.3.
Lemma 2.3 is proven from these; it is the engine that converts intersections into suspensions in Theorem 2.5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the topology of complexes of injective words." pith.science (2026). https://pith.science/paper/SMV563UI

@misc{pith2026190803394,
  author       = {Pith},
  title        = {Pith review of: On the topology of complexes of injective words},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SMV563UI}},
  note         = {Machine review of arXiv:1908.03394}
}

abstract

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

[12]

Reimann MW, Nolte M, Scolamiero M, Turner K, Perin R, Chi ndemi G, D/suppress lotko P, Levi R, Hess K and Markram H (2017), Cliques of Neurons Bound into Cavities Provide a Missing Link between Structure and Function . Front. Comput. Neurosci. 11:48. doi: 10.3389/fncom.2017.00048

arXiv 2017
[1]

Aldous and P

D. Aldous and P. Diaconis, Longest increasing subsequen ces: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36(1999) 413-432

work page 1999
[2]

Brown, Topology and groupoids, BookSurge, LLC, Charleston, SC, 2006

R. Brown, Topology and groupoids, BookSurge, LLC, Charleston, SC, 2006

work page 2006
[3]

Bj¨ orner and M

A. Bj¨ orner and M. L. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277(1983) 323–341

work page 1983
[4]

Bj¨ orner, M

A. Bj¨ orner, M. L. Wachs and V. Welker, Poset ﬁber theorems, Trans. Amer. Math. Soc. 357(2005) 1877–1899

work page 2005
[5]

Dushnik and E

B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63(1941) 600-610

work page 1941
[6]

F. D. Farmer, Cellular homology for posets, Math. Japon. 23(1978/79) 607–613

work page 1978
[7]

Hiraguchi, On the dimension of partially ordered sets , Sci

T. Hiraguchi, On the dimension of partially ordered sets , Sci. Rep. Kanazawa Univ. 1(1951) 77-94

work page 1951

Show all 14 references

[8]

Kozlov, Topology of scrambled simplices, J

D. Kozlov, Topology of scrambled simplices, J. Homotopy Relat. Struct. 14(2019) 371- 391

2019
[9]

B. F. Logan and L. A. Shepp, A variational problem for rand om Young tableaux, Advances in Math. 26(1977) 206-222

1977
[10]

Markram et al., Reconstruction and Simulation of Neoco rtical Microcircuitry, Cell 163, 456-492 October 8, 2015, Elsevier Inc. 14

2015
[11]

Randal-Williams and N

O. Randal-Williams and N. Wahl, Homological stability for automorphism groups, it Advances in Math. 318(2017) 534–626

2017
[13]

Szeg˝ o,Orthogonal polynomials, Third edition, American Mathematical Society Col- loquium Publications, Vol

G. Szeg˝ o,Orthogonal polynomials, Third edition, American Mathematical Society Col- loquium Publications, Vol. 23. American Mathematical Soci ety, Providence, R.I., 1967

1967
[14]

A. M. Vershik and S. V. Kerov, Asymptotic behavior of the Plancherel measure of the symmetric group and the limit form of Young tableaux, Dokl. Akad. Nauk SSSR 233(1977) 1024-1027. 15

1977

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [12]

Reimann MW, Nolte M, Scolamiero M, Turner K, Perin R, Chi ndemi G, D/suppress lotko P, Levi R, Hess K and Markram H (2017), Cliques of Neurons Bound into Cavities Provide a Missing Link between Structure and Function . Front. Comput. Neurosci. 11:48. doi: 10.3389/fncom.2017.00048

arXiv 2017

[2] [1]

Aldous and P

D. Aldous and P. Diaconis, Longest increasing subsequen ces: from patience sorting to the Baik-Deift-Johansson theorem, Bull. Amer. Math. Soc. (N.S.) 36(1999) 413-432

work page 1999

[3] [2]

Brown, Topology and groupoids, BookSurge, LLC, Charleston, SC, 2006

R. Brown, Topology and groupoids, BookSurge, LLC, Charleston, SC, 2006

work page 2006

[4] [3]

Bj¨ orner and M

A. Bj¨ orner and M. L. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277(1983) 323–341

work page 1983

[5] [4]

Bj¨ orner, M

A. Bj¨ orner, M. L. Wachs and V. Welker, Poset ﬁber theorems, Trans. Amer. Math. Soc. 357(2005) 1877–1899

work page 2005

[6] [5]

Dushnik and E

B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63(1941) 600-610

work page 1941

[7] [6]

F. D. Farmer, Cellular homology for posets, Math. Japon. 23(1978/79) 607–613

work page 1978

[8] [7]

Hiraguchi, On the dimension of partially ordered sets , Sci

T. Hiraguchi, On the dimension of partially ordered sets , Sci. Rep. Kanazawa Univ. 1(1951) 77-94

work page 1951