A Problem of Erdös Concerning Lattice Cubes

Abstract

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 $\alpha (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\le k\le n$? We discover some interesting formulas and asymptotic patterns that shed new light on the question.