An extremal problem on crossing vectors.

Abstract: For positive integers

w

and

k

, two vectors

A

and

B

from

m a t h b b Z^{w}

are called

k

-crossing if there are two coordinates

i

and

j

such that

A [i] - B [i] g e q k

and

B [j] - A [j] g e q k

. What is the maximum size of a family of pairwise

1

-crossing and pairwise non-

k

-crossing vectors in

m a t h b b Z^{w}

? We state a conjecture that the answer is

k^{w - 1}

. We prove the conjecture for

w l e q 3

and provide weaker upper bounds for

w g e q 4

. Also, for all

k

and

w

, 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.

Recommendations

Cites Work

Cited In (1)

This page was built for publication: An extremal problem on crossing vectors.