Two combinatorial problems on posets |
| |
Authors: | Yair Caro |
| |
Institution: | (1) Department of Mathematics, School of Education, University of Haifa-Oranim, 36006 Tivon, Israel |
| |
Abstract: | Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z
k
-coloring f: P Z
k
there exists either a chain or an antichain A, |A|=n and
aA
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)2–c(k) p(n, k) (n+k–2)2+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös 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). |
| |
Keywords: | 06A10 05A05 05C55 |
本文献已被 SpringerLink 等数据库收录! |
|