The number of \(k\)-dimensional corner-free subsets of grids

Younjin Kim¹

¹Ewha Womans University

The electronic journal of combinatorics, Tome 29 (2022) no. 2

Résumé

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))$.

Détail

DOI : 10.37236/9424

Classification : 05D05
Mots-clés : Szemerédi's theorem, \(k\)-dimensional corner-free subsets of a grid