2020/11/30 by Chengcheng Yang, Yang, Chengcheng
Computer Science · Mathematics · #Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #Digital Image Processing Techniques #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2011.15010
openalex publication_date 2020/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies a problem of Erdös concerning lattice cubes. Given an N × N × 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(N11/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 × n grid is also an n × 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 × n matrix with entries 0 and 1, such that every k × k minor contains at least one entry of 1, for 1 ≤ k ≤ n? We discover some interesting formulas and asymptotic patterns that shed new light on the question.