An Extremal Problem for Finite Lattices

Abstract

For a fixed M x N integer lattice L(M,N), we consider the maximum size of a subset A of L(M,N) which contains no squares of prescribed side lengths k(1),...,k(t). We denote this size by ex(L(M,N), {k(1),...,k(t)}), and when t = 1, we abbreviate this parameter to ex(L(M,N), k), where k = k(1). Our first result gives an exact formula for ex(L(M,N), k) for all positive integers k, M, and N, where ex(L(M,N), k) = ((3/4) + o(1)) MN holds for fixed k and diverging M and N. Our second result identifies a subset A0 of L(M,N) of size at least (2/3)MN with the property that, for any integer k not divisible by three, A0 contains no squares of side length k. Our third result shows that |A0| is asymptotically best possible, in that for all positive integers M and N, we have ex(L(M,N), {1,2}) MN + O(M+N). When M = 3m, our estimates on the error above render exact formulas for ex(L(3m,3), {1,2}) and ex(L(3m,6), {1,2}).

Keywords

• extremal combinatorics
• lattices