Abstract: | Let sk(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an sk(n)-point semiorder. When k = 1, s1(n) = n since all interval orders with no two-point antichains are chains. Given (c1,...,c5) = (1, 2, 3, 4), it is shown that s2(n) = cn for n 4, s3(n) = cn for n 5, and for all positive n, s2 (n+4) =s2(n)+3, s3(n+5) = s3(n)+3. Hence s2 has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s3 has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...]. Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern. |