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.


Published in:
Journal Of Combinatorial Theory Series A, 128, 41-55
Year:
2014
Publisher:
San Diego, Academic Press Inc Elsevier Science
ISSN:
0097-3165
Keywords:
Laboratories:




 Record created 2014-12-30, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)