Two combinatorial problems on posets
type: Item
instance of: scholarly article
title: Two combinatorial problems on posets
zbMATH Open document ID: 0860.06002
DOI: 10.1007/BF00383966
author: Yair Caro
published in: Order
publication date: 1997-04-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 947541
zbMATH Keywords: partially ordered set
zbMATH Keywords: zero-sum
zbMATH Keywords: monotone sequences
Wikidata QID: Q71671620
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q4284607
cites work: On zero-sum Ramsey numbers--stars
cites work: Zero-sum subsequences in Abelian non-cyclic groups
cites work: A decomposition theorem for partially ordered sets
cites work: Q5759552
cites work: On the Erdös-Ginzburg-Ziv theorem
Recommended article: Two combinatorial problems in the plane
Recommended article: Q3231171
Recommended article: Counting two-dimensional posets
Recommended article: Q4714215
Recommended article: Q3189184
Recommended article: Combinatorial problems raised from 2-semilattices
Recommended article: Two combinatorial problems in group theory
Recommended article: Two Combinatorial Problems in Group Theory
description: scientific article; zbMATH DE number 947541