论文标题
r^d中最大邻居框数的新界限
New bounds on the maximum number of neighborly boxes in R^d
论文作者
论文摘要
如果其中两个的相交的尺寸至少至少$ d-k $，最多只有$ d-1 $，则$ \ er^d $中的轴对准盒子是\ er^d $ is \ emph {$ k $ -neighborly}。令$ n（k，d）$表示这样一个家庭的最大规模。众所周知，$ n（k，d）$可以等效地定义为完整图中的最大顶点数量，其边缘可以由$ d $完整的两部分图覆盖，每个边缘最多覆盖为$ k $ times。 我们在$ n（k，d）$上得出了一种新的上限，特别是暗示$ n（k，d）\ leqslant（2-δ）^d $如果$ k \ leqslant（1- \ varepsilon）d $，其中$ uexuduectiony $δ> 0 $取决于任意选择的$ \ VAREPSILON $ \ VAREPSILON> 0 $ 0 $ 0。该证明应用了Kleitman的经典结果，涉及离散高管中给定直径的最大集合大小。通过明确的结构，我们还获得了$ n（k，d）$的新下限，这意味着$ n（k，d）\ geqslant（1-o（1））\ frac {d^k} {k！} $。我们还研究了$ k $ - 尼加利利的盒子家族，并具有其他结构性特性。以树状的方式分裂的家庭称为\ emph {total laminations}，对于显式结构特别有用。我们根据这些结构和一些计算实验提出了一些猜想。
A family of axis-aligned boxes in $\er^d$ is \emph{$k$-neighborly} if the intersection of every two of them has dimension at least $d-k$ and at most $d-1$. Let $n(k,d)$ denote the maximum size of such a family. It is known that $n(k,d)$ can be equivalently defined as the maximum number of vertices in a complete graph whose edges can be covered by $d$ complete bipartite graphs, with each edge covered at most $k$ times. We derive a new upper bound on $n(k,d)$, which implies, in particular, that $n(k,d)\leqslant (2-δ)^d$ if $k\leqslant (1-\varepsilon)d$, where $δ>0$ depends on arbitrarily chosen $\varepsilon>0$. The proof applies a classical result of Kleitman, concerning the maximum size of sets with a given diameter in discrete hypercubes. By an explicit construction we obtain also a new lower bound for $n(k,d)$, which implies that $n(k,d)\geqslant (1-o(1))\frac{d^k}{k!}$. We also study $k$-neighborly families of boxes with additional structural properties. Families called \emph{total laminations}, that split in a tree-like fashion, turn out to be particularly useful for explicit constructions. We pose a few conjectures based on these constructions and some computational experiments.
