3
$\begingroup$

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.

$\endgroup$
4
  • 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

0

Reset to default

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.