Exact values and improved bounds on k-neighborly families of boxes

Abstract: A finite family

m a t h c a l F

of

d

-dimensional convex polytopes is called

k

-neighborly if

d - k l e e x t u p d i m (C c a p C^{'}) l e d - 1

for any two distinct members

C, C^{'} i n m a t h c a l F

. In 1997, Alon initiated the study of the general function

n (k, d)

, which is defined to be the maximum size of

k

-neighborly families of standard boxes in

m a t h b b R^{d}

. Based on a weighted count of vectors in

{0, 1}^{d}

, we improve a recent upper bound on

n (k, d)

by Alon, Grytczuk, Kisielewicz, and Przesl awski for any positive integers

d

and

k

with

d g e k + 2

. In particular, when

d

is sufficiently large and

k g e 0.123 d

, our upper bound on

n (k, d)

improves the bound

shown by Huang and Sudakov exponentially. Furthermore, we determine that

n (2, 4) = 9

,

n (3, 5) = 18

,

n (3, 6) = 27

,

n (4, 6) = 37

,

n (5, 7) = 74

, and

n (6, 8) = 150

. The stability result of Kleitman's isodiametric inequality plays an important role in the proofs.

Recommendations

Cites Work

Cited In (1)

This page was built for publication: Exact values and improved bounds on \(k\)-neighborly families of boxes