REVIEW 3 major objections 5 minor 8 references
The Relation between Composability and Splittability of Permutation Classes
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper shows that the permutation class $I[D[I]]$ is composable but unsplittable, settling an open question about the relation between the two properties.
desk verdict A genuine answer to Karpilovskij's question, with a clean construction; the main result holds up, but several proofs are too terse and need repair. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The mechanism that carries the argument is the inflation operation, in which each point of one permutation is replaced by a block from another permutation class, together with the lemma that the inflation of unsplittable classes is unsplittable. The class $C = I[D[I]]$ is obtained by inflating an increasing permutation by blocks from $D[I]$, and the lemma transfers unsplittability from $I$ and $D$ up to $C$. For composability, the direct-sum structure of $C$ is exploited: reversing each block of an element turns it into a layered permutation, and composing with a direct sum of decreasing permutations of matching block lengths produces the original element, so $C$ is contained in $L \circ L$ with $L = I[D]$ the layered class. For the positive splittability theorem, a composition lemma bounds the length of decreasing subsequences in a composition of two pattern-avoiding classes, which lets a $k$-fold composition be rewritten as a merge of copies of a single proper subclass.
What would settle it
Show a split of $C=I[D[I]]$: find proper subclasses $A,B\subsetneq C$ such that every element of $C$ can be colored red and blue with the red subsequence in $A$ and the blue subsequence in $B$. Equivalently, by the paper's Proposition 2.1, find patterns $\pi,\pi'\in C$ such that every element of $C$ has a two-coloring with no red $\pi$ and no blue $\pi'$. Finding such a split would disprove Theorem 3.1.
Extended reading notes
Core claim
The paper's central discovery is that composability does not imply splittability: the class $C=I[D[I]]$ is composable and unsplittable. The classes $I$ and $D$ of all increasing and all decreasing permutations are unsplittable because each has exactly one permutation of each length, and the inflation lemma passes unsplittability to $C$. At the same time, every element of $C$ is a composition of two layered permutations, so $C$ lies inside $L\circ L$ for a proper subclass $L$; hence $C$ is composable. The paper also proves a partial converse: an infinite composable class that avoids some increasing or decreasing permutation must be splittable, so the new example necessarily contains arbitrarily long increasing and decreasing permutations.
Load-bearing premise
The unsplittability of $I$ and $D$, and hence of $C$, rests on the fact that these classes have exactly one permutation of each length, so every proper subclass has bounded length and two proper subclasses cannot together cover arbitrarily long increasing or decreasing permutations; this fact is used without proof.
Editorial extensions
If this is right
- The two notions of decomposability are independent: each of the four combinations of composable/uncomposable and splittable/unsplittable is now realized by some permutation class.
- Every infinite composable class that avoids some finite increasing or decreasing pattern is splittable, so any further composable unsplittable examples must contain arbitrarily long increasing and decreasing permutations.
- The class $I[D[I]]$ is covered by two copies of the layered class under composition, giving a concrete class whose members have a two-factor factorization by layered permutations.
- The inflation lemma provides a reusable way to build unsplittable classes from unsplittable components, so classes of the form $A[B]$ with $A,B$ unsplittable are immediately unsplittable.
Reading between the lines
- A natural next test is whether other inflations, such as $D[I[D]]$ or iterated inflations $I[D[I[D]]]$, remain composable while unsplittable; the same inflation lemma would preserve unsplittability if the base classes do.
- The proof of Theorem 3.3 separates even from odd numbers of composition factors; this suggests that composability by an odd number of proper subclasses may be the only route to novel unsplittable examples, and questions about $k$-composability for odd $k$ are where new obstructions would appear.
- Because $C$ is written as $L\circ L$ with $L$ a proper subclass, ordinary splittability is not needed to cover it; this example could be used to compare other decomposition notions, such as exact-splittability, on a class that is unsplittable in the merge sense.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies two decomposability notions for permutation classes: splittability (red-blue coloring into two proper hereditary subclasses) and composability (factorization under permutation composition into proper subclasses). The main result, Theorem 3.1, exhibits the class C = I[D[I]] and proves that it is composable but not splittable, thereby answering a question of Karpilovskij. The secondary result, Theorem 3.3, states that every infinite composable class avoiding an increasing or a decreasing permutation is splittable. The paper also introduces the notion of exact-splittability and poses several open questions.
Significance. If correct, Theorem 3.1 is the first example separating composability from splittability, a natural distinction in the area, and the construction via inflations is elegant. Theorem 3.3 gives a useful sufficient condition under which the two notions coincide. The paper is self-contained and does not rely on any numerical fitting; the core arguments use standard tools such as the Erdős–Szekeres theorem and known results on unsplittable classes. I regard the results as significant for the permutation-class community.
major comments (3)
- [Section 3.1, Theorem 3.1] The inference 'there are no proper infinite subclasses, so I and D are unsplittable' is not valid as stated; finiteness of all proper subclasses does not by itself rule out a split into two finite proper subclasses (for example, the finite class {1,12,21} is splittable via {1,12} and {1,21}). The missing step is that a proper subclass of I omits some ι_N and hence has bounded length, so a merge of two such subclasses has bounded length and cannot contain ι_N for arbitrarily large N; the analogous argument holds for D. Since Lemma 2.3 is then used to transfer unsplittability to C=I[D[I]], this step is load-bearing and should be written out.
- [Section 3.2, Lemma 3.2] The proof of the bound A∘B⊆I_{kℓ} contains a false equivalence. After defining α′ and β′, the text states that for u<v, β′_u<β′_v if and only if α′_{β′_u}>α′_{β′_v}. The reverse direction is false: for α=132, β=21, γ=α∘β=31, the decreasing subsequence at positions 1,2 gives β′=21 and α′=12 (with the natural sorted restriction), so β′_1<β′_2 is false while α′_{β′_1}>α′_{β′_2} is true. What the proof needs is only the forward implication, which yields that any increasing subsequence of β′ gives a decreasing subsequence of α of the same length; together with the fact that any decreasing subsequence of β′ is a decreasing subsequence of β, Erdős–Szekeres gives m≤kℓ. The definitions of α′ and β′ should also be spelled out, since the equality δ_m=α′∘β′ depends on taking α′ from the sorted indices rather than from the listed order.
- [Section 3.3, Theorem 3.3] The step 'C⊆A1∘I_{m^{k-1}} implies C is the merge of m^{k-1} copies of A1' relies on the asserted fact that composing a permutation with an element of I_n is equivalent to de-merging it into at most n subpermutations. This fact is stated without proof and the referenced figure is missing. A proof is necessary: if π=α∘η with η∈I_n, partition the positions of η into at most n increasing subsequences (possible because η has no decreasing subsequence of length n+1); each color class induces a subsequence of π that is a subpermutation of α and hence lies in A1. Without this argument, the splittability conclusion of Theorem 3.3 does not follow.
minor comments (5)
- [Section 1] The name 'Steinrímsson' should be 'Steingrímsson'.
- [Section 2.1] The phrase 'a fixed set set of permutations' contains a duplicated word.
- [Section 3.1, Theorem 3.1] The notation π^r_i in the composability proof should be defined explicitly as the reversal of the block π_i, rather than left ambiguous with the reversal of the whole permutation.
- [Section 3.3] The quantity 'δmk+1' should be typeset as δ_{m^k+1}, and the superscripts in I_{m^{k-1}} should be rendered unambiguously.
- [Section 3.3] The reference 'see Figure??' should be resolved: either the figure should be included or the reference removed.
Circularity Check
No circularity; the derivation is self-contained against external benchmarks and contains no fitted parameters.
full rationale
The paper's central claim is that C = I[D[I]] is composable but unsplittable. The unsplittability of I and D is argued from the fact that each contains exactly one permutation of each length, so proper subclasses are finite; the missing bounded-length step is an omitted justification, not a circular reduction. Lemma 2.3 is quoted from external work [2] and independently reproved in the paper, so the reliance is not a self-citation chain. Composability of C is shown by an explicit construction with α and β in L = I[D], and the containment C ⊆ L∘L is verified by direct composition. The splittability results in Theorem 3.3 rely on the external Erdős–Szekeres theorem and on Lemma 3.2, which is proved in the paper. There are no fitted parameters, no quantity is defined in terms of the predicted quantity, and no known result is merely renamed. The omission of the bounded-length argument in Theorem 3.1 is a completeness concern, not circularity.
Assumptions & free parameters
assumptions (4)
- standard math Erdos-Szekeres theorem, that any sequence of length (k-1)(l-1)+1 contains an increasing subsequence of length k or a decreasing subsequence of length l
- domain assumption Unsplitability implies atomicity (Corollary 2.2 from [7])
- standard math Dilworth's theorem, that a permutation with no decreasing subsequence of length n+1 can be partitioned into n increasing subsequences
- domain assumption Inflation of unsplittable classes preserves unsplittability (Lemma 2.3)
Cite this review
Pith. "Pith review of The Relation between Composability and Splittability of Permutation Classes." pith.science (2026). https://pith.science/paper/M7EV5PWD
@misc{pith2026190802731,
author = {Pith},
title = {Pith review of: The Relation between Composability and Splittability of Permutation Classes},
year = {2026},
howpublished = {\url{https://pith.science/paper/M7EV5PWD}},
note = {Machine review of arXiv:1908.02731}
}
abstract
A permutation class $C$ is said to be splittable if there exist two proper subclasses $A, B \subsetneq C$ such that any $\sigma \in C$ can be red-blue colored so that the red (respectively, blue) subsequence of $\sigma$ is order isomorphic to an element of $A$ (respectively, $B$). The class $C$ is said to be composable if there exists some number of proper subclasses $A_1, \dots, A_k \subsetneq C$ such that any $\sigma \in C$ can be written as $\alpha_1 \circ \dots \circ \alpha_k$ for some $\alpha_i \in A_i$. We answer a question of Karpilovskij by showing that there exists a composable permutation class that is not splittable. We also give a condition under which an infinite composable class must be splittable.
Figures
Reference graph
Works this paper leans on
-
[7]
V. Jelínek & P. Valtr. Splittings and Ramsey properties of permutation classes.Advances in Applied Mathematics, 63, 41-67, 2015
work page 2015
-
[8]
M. Karpilovskij. Composability of permutation classes.The Electronic Journal of Combinatorics , 26(1), 2019, P1.41. Department of Mathematics, MIT, Cambridge, MA 02139, USA Email address: rachelyz44@gmail.com
work page 2019
-
[1]
M. H. Albert, R. E. L. Aldred, M. D. Atkinson, H. P. van Ditmarsch, C. C. Handley, D. A. Holton, & D. J. McCaughan. Compositions of pattern restricted sets of permutations.Australasian Journal Of Combinatorics , 37:43–56, 2007
work page 2007
-
[2]
M. Albert & V. Jelínek. Unsplittable classes of separable permutations.The Electronic Journal of Combinatorics , 23(2), 2016, P2.49
work page 2016
-
[3]
M. D. Atkinson and T. Stitt. Restricted permutations and the wreath product.Discrete Mathematics, 259:19–36, 2002
work page 2002
-
[4]
A. Claesson, V. Jelínek, & E. Steingrímsson. Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. Journal of Combinatorial Theory, Series A , 119:1680–1691, 2012
work page 2012
- [5]
-
[6]
V. Jelínek & M. Opler. Splittability and 1-amalgamability of permutation classes. Discrete Mathematics and Theoretical Computer Science, 19(2), 2017
work page 2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.