Two combinatorial problems on posets (Q1815848): Difference between revisions

The EGZ-theorem states that if \(n\geq k\geq 2\), \(k/n\) and \(A=\{a_1,\dots, a_{n+k-1}\}\) is a sequence of integers, then for some subset \(I\subseteq \{1,2,\dots, n+k-1\}\), \(|I|=n\) and \(\sum_{i\in I}a_i\equiv 0\pmod k\). Based on this result, many zero-sum theorems can be usefully considered. In this paper, the author, a practitioner, estimates \(p(n,k)\), the least positive integer such that for every poset \(P\), \(|P|\geq p(n,k)\), and every \(Z_k\)-coloring \(f:P\to Z_k\), there exists either a chain or an antichain \(A\), \(|A|=n\) and \(\sum_{a\in A}f(a)\equiv 0\pmod k\). Indeed, he proves that there exists a constant \(c(k)\) depending on \(k\), such that \((n+k-2)^2- c(k)\leq p(n,k)\leq (n+k-2)^2+1\). Thus, obvious easy choices depending on both \(n\) and \(k\) are immediately irrelevant and asymptotic estimates with respect to \(n\) become trivial. He then also uses a quite clever definition to define a poset which along with the earlier result provides the mechanism of proof to demonstrate the existence of 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 and all columns monotone sequences, generalizing a celebrated result of Erdös-Szekeres.