The permutation pattern poset is not Sperner
- Kind
- Counterexample (a finite check) plus an exact family (a written proof)
- Status
- Counterexample checked by five programs; family proved in writing by agents, read line by line by two more, computer-checked for k = 1 to 8; unrefereed
- Prior work
- Not found in the searches logged; Pouzet–Rosenberg 1986 and the Burosch papers of 1990 and 1996 unread
On this page
The statement
A pattern of a permutation is what some of its entries spell when kept in place and renumbered: keeping 2, 1 and 3 of 2413 spells 213. Ordering all permutations by "is a pattern of" gives the permutation pattern poset. An interval is every permutation that contains and is contained in ; a level is its members of one length. An antichain is a set none of which contains another, and the poset is Sperner when its largest antichain is no bigger than its largest level.
McNamara and Steingrímsson, "On the topology of the permutation pattern poset" (J. Combin. Theory Ser. A, 2015), Question 9.5:
"Are all intervals in P Sperner? If so, are they strongly Sperner?"
Theorem.
- (The counterexample.) The interval has levels of sizes 1, 3, 7, 7, 1 but an antichain of 8.
- (The exact family.) For let and then every other number from down to . The patterns of have width and largest level , so they beat their largest level by exactly .
So the answer to the first half of Question 9.5 is no, and the excess is unbounded, even for principal downsets .
Check it yourself
The interval , all 19 members:
| length | members |
|---|---|
| 3 | 213 |
| 4 | 1324 2413 3241 |
| 5 | 13524 14352 24351 24513 25413 35241 43512 |
| 6 | 146352 246351 246513 254613 256413 264513 463512 |
| 7 | 2574613 |
The antichain of 8: 13524 14352 24351 35241 43512 (length 5) and 246513 256413 264513 (length 6).
By hand. Two patterns of one length cannot contain each other. A length-6 pattern contains a length-5 one exactly when deleting one entry gives it. Delete each entry of 246513 in turn: 35412, 25413, 24513, 24513, 13542, 23541. Of these only 24513 and 25413 lie in the interval, and neither is among the five. The same holds for 256413 and 264513. So the three length-6 patterns sit above only two length-5 patterns; swap those two out of the level of 7 for the three above them, and .
The family at : has 81 patterns in levels 1, 1, 2, 5, 9, 14, 16, 16, 11, 5, 1, so the largest level is 16; the width is 17.
Worked examples
Why the family works. Call three entries a valley when the middle one is lowest. A pattern of that keeps both leaders and a tail value above has a valley; the rest have none, and having a valley passes up to anything larger. The valley patterns peak at length with members; the valley-free ones keep growing and number at length . Together these form an antichain of . A cover of all the patterns by exactly that many chains shows nothing larger exists.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
| 10 | 16 | 22 | 28 | 34 | 40 | 46 | 52 | |
| patterns | 81 | 265 | 609 | 1,161 | 1,969 | 3,081 | 4,545 | 6,409 |
| largest level | 16 | 33 | 56 | 85 | 120 | 161 | 208 | 261 |
| width | 17 | 35 | 59 | 89 | 125 | 167 | 215 | 269 |
Status and who checked it
- The counterexample: a finite check, complete. The 8 patterns, checked pair by pair, by at least five programs written by agents. No interval with of length 6 or less fails; at length 7 exactly 16 of the 189,524 intervals fail, all with width 8 against 7; at length 8, 766 of 2,767,428 fail.
- The exact family: a written proof by agents. A falsifier agent proved the lower bound (excess at least ); a separate agent's review added the matching chain cover and the exact largest level. A reviewer agent and a verifier agent read the proofs line by line ("No gap found in either proof"; "PROOF HOLDS"). Checked by computer for to 8 by two separate programs, and for by more.
- Open: how fast the largest excess over all permutations of length grows (searches found 12 at and 28 at , far above the family's ), and whether width over largest level is bounded. The rank-unimodality conjectures beside the question are untouched.
- Unrefereed. No human has read either proof.
Prior work
Searches run. A falsifier agent logged 33 searches that answered and read 12 candidates; a reviewer agent logged 26 and read 14, with hand searches of Zenodo, DataCite, HAL, OSF and GitHub and Jason Smith's 2015 thesis on the pattern poset. Elizalde and McNamara proved the consecutive pattern poset strongly Sperner and wrote "neither result is known for the classical pattern poset". A keyed CORE run on 2026-11-20 (7 requests, 15 records) found no record of a non-Sperner interval of the classical pattern poset. The result was not found in the searches logged. On 2026-11-22, a Google Scholar sweep (5 queries) found no prior work stating this claim.
Still owed: Pouzet and Rosenberg, "Sperner properties for groups and relations" (1986), is unread (publisher refused); a non-Sperner example of permutations there would be prior work for the downset part. Burosch, Gronau, Laborde and Warnke (1996) and Burosch, Franke and Roehl (1990), on subword posets of binary words (a special case of principal downsets here), are unread. Kitaev's and Bóna's books and the Permutation Patterns abstract booklets were not searched.
Further reading
- McNamara and Steingrímsson, "On the topology of the permutation pattern poset", J. Combin. Theory Ser. A 134 (2015); arXiv:1305.5569.
- Elizalde and McNamara, "On intervals of the consecutive pattern poset", arXiv:1508.05963.
- Vatter, problem list (2026), arXiv:2602.16355: Conjecture 2.1, on rank-unimodal downsets.