# Prove every permutation of the alphabet contains a subset of six letters in order

Prove that no matter the arrangement of the alphabet you can find a subset of six letters in alphabetical order, read from left to right or right to left.

For example the permutation {g,w,z,c,d,p,i,b,y,t,a,n,u,e,r,j,l,x,s,v,m,f,q,k,h,o} contains the subset {a,e,j,l,m,q}.

I know I have to construct a partially ordered set and possibly use Dilworth's Theorem, however I don't know how to begin tackling this problem.

• Check Erdos Szekeres theorem. Sep 1, 2021 at 8:21
• Is there a known example for $n=7$?
– JMP
Sep 1, 2021 at 8:27
• Dilworth's theorem is definitely the way to go. Consider a chain decomposition. Either it contains a chain of length more than 5, or there must be more than 5 chains (since $5\cdot 5<26$) and therefore an antichain of length more than 5. The trick is to come up with the right partial order. Good call on Dilworth's theorem.
– MJD
Sep 1, 2021 at 8:42
• cut-the-knot.org/pigeonhole/seq.shtml Sep 1, 2021 at 9:52