×

An extremal problem for finite lattices. (English) Zbl 1468.06008

Summary: For a positive integer \(k\), a \(k\)-square \(S_k\) (more generally, a square) in \(\mathbb Z\times\mathbb Z\) is any set \(\{(i,j),(i+k,j),(i,j+k), (i+k,j+k)\}\subset\mathbb Z\times\mathbb Z\). Let \(S_k\) denote the class of \(k\)-squares \(S_k\subset\mathbb Z\times\mathbb Z\). A set \(A\subset\mathbb Z\times \mathbb Z\) is said to be \(S_k\)-free if, for each \(S_k\in S_k\), we have that \(S_k\nsubseteq A\). For positive integers \(M\) and \(N\), let \(L_{M,N}= [0,M-1]\times[0,N-1]\) be the \(M\times N\) non-negative integer lattice. For positive integers \(k_1,\dots, k_\ell\), set \[\mathrm{ex}(L_{M,N}, \{S_{k_1},\dots,S_{k_\ell}\})= \max\{|A|:A \subseteq L_{M,N}\text{ is } S_{k_i}\text{-free for all }1\le i\le\ell\}\] and when \(\{S_{k_1},\dots, S_{k_\ell}\}=\{S_k\}\), we abbreviate this parameter to \(\mathrm{ex} (L_{M,N},S_k)\).
Our first result gives an exact formula for \(\mathrm{ex}(L_{M,N},S_k)\) for all integers \(k,M,N\ge 1\), where \(\mathrm{ex} (L_{M,N},S_k)=(3/4+o(1))MN\) holds for fixed \(k\) and \(\min\{M,N\}\to \infty\). Our second result identifies a set \(A_0\subset L_{M,N}\) of size \(|A_0|\ge(2/3)MN\) with the property that, for any integer \(k\not\equiv 0\mod 3\), \(A_0\) is \(S_k\)-free. Our third result shows that \(|A_0|\) is asymptotically best possible, in that for all integers \(M,N\ge 1\), \(\mathrm{ex}(L_{M,N},\{S_1,S_2\})\le(2/3) MN+O(M+N)\). When \(M=3m\) is divisible by three, our estimates on the error \(O(M+N)\) render exact formulas for \(\mathrm{ex}(L_{3m,3},\{S_1,S_2\})\) and \(\mathrm{ex}(L_{3m,6},\{S_1,S_2\})\).

MSC:

06B05 Structure theory of lattices
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI