Natalie Behague

Counting copies with containers

If X is a finite subset of \mathbb{N}^d then what is the maximum size of a subset of \{1,...,n\}^d that does not contain a scaled and/or translated copy of X? Let r_X(n) denote this quantity. The Multidimensional Szemeredi Theorem (due to Furstenberg and Katznelson) states that r_X(n) = o(n^d), although r_X(n) is not known more precisely.
A follow-up question is, how many such X-free subsets of \mathbb{N}^d are there? Clearly, there are at least 2^{r_X(n)}, by taking all subsets of a maximal one. We use the powerful hypergraph container lemma to show that for any |X| >= 3 and infinitely many n \in\mathbb{N}, the number of X-free subsets of \{1,...,n\}^d is at most 2^{O(r_X(n))}. This generalises work of Balogh, Liu, and Sharifzadeh on k-AP-free sets and Kim on corner-free sets.

This is joint work with Joseph Hyde, Natasha Morrison, Jonathan A. Noel and Ashna Wright.