Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655259 | Journal of Combinatorial Theory, Series A | 2014 | 15 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak,