Two combinatorial problems on posets

✍ Scribed by Yair Caro

• Publisher: Springer Netherlands
• Year: 1996
• Tongue: English
• Weight: 367 KB
• Volume: 13
• Category: Article
• ISSN: 0167-8094
• DOI: 10.1007/bf00383966

✦ Synopsis

Bialostocki proposed the following problem: Let n 2 k 2 2 be integers such that k/n. Let p(n, k) denote the least positive integer having the property that for every poset P, IPI > p(n, k) and every &coloring f: P + & there exists either a chain or an antichain A, (Al = n and xaEA f(a) = 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n + k -2)*c(k) < p(n, k) < (n + k -2)' + 1. Another problem considered here is a 2dimensional form of the monotone sequence theorem of Erdos and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).