The Number of $k$-Dimensional Corner-Free Subsets of Grids

  • Younjin Kim


A subset $A$ of the $k$-dimensional grid $\{1,2, \dots, N\}^k$ is said to be $k$-dimensional corner-free if it does not contain a set of points of the form $\{ \textbf{a} \} \cup \{ \textbf{a} + de_i : 1 \leq i \leq k \}$ for some $\textbf{a} \in \{1,2, \dots, N\}^k$ and $d > 0$, where $e_1,e_2, \ldots, e_k$ is the standard basis of $\mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of $\{1,2, \ldots, N\}^k$ as $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid $\{1,2, \dots, N\}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tools for proof are the hypergraph container method and the supersaturation result for $k$-dimensional corners in sets of size $\Theta(c_k(N))$.

Article Number