论文标题
Erdös关于格子立方体的问题
A Problem of Erdös Concerning Lattice Cubes
论文作者
论文摘要
本文研究了Erdös关于晶格立方体的问题。给定一个$ n \ times n \ times n $晶格立方体，我们想找到一个可以选择的最大顶点，以便同时选择矩形盒的八个角。 Erdös猜想它具有尖锐的上限，即$ O（N^{11/4}）$，但还没有发现大的例子。我们开始使用精疲力尽的方法来解决小$ n $的问题，我们发现不一定有独特的最大顶点集（计算所有可能的对称性）。接下来，我们研究此问题的等效二维版本，寻找可能有助于概括为三维情况的模式。 Since an $n \times n$ grid is also an $n \times n$ matrix, we rephrase and generalize the original question to: what is the minimum number $α(k,n)$ of vertices one can put in an $n \times n$ matrix with entries 0 and 1, such that every $k \times k$ minor contains at least one entry of 1, for $1 \leq k \leq n$?我们发现了一些有趣的公式和渐近模式，这些图案为这个问题提供了新的启示。
This paper studies a problem of Erdös concerning lattice cubes. Given an $N \times N \times N$ lattice cube, we want to find the maximum number of vertices one can select so that no eight corners of a rectangular box are chosen simultaneously. Erdös conjectured that it has a sharp upper bound, which is $O(N^{11/4})$, but no example that large has been found yet. We start approaching this question for small $N$ using the method of exhaustion, and we find that there is not necessarily a unique maximal set of vertices (counting all possible symmetries). Next, we study an equivalent two-dimensional version of this problem looking for patterns that might be useful for generalizing to the three-dimensional case. Since an $n \times n$ grid is also an $n \times n$ matrix, we rephrase and generalize the original question to: what is the minimum number $α(k,n)$ of vertices one can put in an $n \times n$ matrix with entries 0 and 1, such that every $k \times k$ minor contains at least one entry of 1, for $1 \leq k \leq n$? We discover some interesting formulas and asymptotic patterns that shed new light on the question.
