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.

  • 1
    $\begingroup$ Check Erdos Szekeres theorem. $\endgroup$
    – Phicar
    Sep 1, 2021 at 8:21
  • $\begingroup$ Is there a known example for $n=7$? $\endgroup$
    – JMP
    Sep 1, 2021 at 8:27
  • 4
    $\begingroup$ 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. $\endgroup$
    – MJD
    Sep 1, 2021 at 8:42
  • $\begingroup$ cut-the-knot.org/pigeonhole/seq.shtml $\endgroup$
    – Math Lover
    Sep 1, 2021 at 9:52


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.