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

Abstract

In 1975, Szemeredi proved that for every real number $\delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of the set ${1, 2, \cdots, N }$ with $|A| \geq \delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemeredi’s theorem in many areas of mathematics. In 1990, Cameron and Erdos proposed a conjecture about counting the number of subsets of the set ${1,2, \dots, N}$ which do not contain an arithmetic progression of length $k$. In the talk, we study a natural higher dimensional version of this conjecture by counting the number of subsets of the $k$-dimensional grid ${1,2, \dots, N}^k$ which do not contain a $k$-dimensional corner that is a set of points of the
form ${ a } \cup { a+ de_i : 1 \leq i \leq k }$ for some $a \in {1,2, \dots, N}^k$ and $d > 0$, where $e_1,e_2, \cdots, e_k$ is the standard basis of $\mathbb{R}^k$. 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))$, where $c_k(N)$ is the maximum size of a $k$-dimensional corner-free subset of ${1,2, \dots, N}^k$.