Journal article

An extremal problem on crossing vectors

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Z(w)? We state a conjecture that the answer is k(w-1). We prove the conjecture for w <= 3 and provide weaker upper bounds for w >= 4. Also, for all k and so, we construct several quite different examples of families of desired size k(w-1). This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set. (C) 2019 Elsevier Inc. All rights reserved.


Related material