Article ID Journal Published Year Pages File Type
4655259 Journal of Combinatorial Theory, Series A 2014 15 Pages PDF
Abstract

For positive integers w and k, two vectors A and B   from ZwZw are called k-crossing if there are two coordinates i and j   such that A[i]−B[i]≥kA[i]−B[i]≥k and B[j]−A[j]≥kB[j]−A[j]≥k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k  -crossing vectors in ZwZw? We state a conjecture that the answer is kw−1kw−1. We prove the conjecture for w≤3w≤3 and provide weaker upper bounds for w≥4w≥4. Also, for all k and w  , we construct several quite different examples of families of desired size kw−1kw−1. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,