The number of kk-dimensional corner-free subsets of grids

preprint2022arXivOpen access

Abstract

A subset AA of the kk-dimensional grid {1,2,⋯ ,N}k\{1,2, \cdots, N\}^k is called kk-dimensional corner-free if it does not contain a set of points of the form {a}∪{a+dei:1≤i≤k}\{ a \} \cup \{ a + de_i : 1 \leq i \leq k \} for some a∈{1,2,⋯ ,N}ka \in \{1,2, \cdots, N\}^k and d>0d > 0, where e1,e2,⋯ ,eke_1,e_2, \cdots, e_k is the standard basis of Rk\mathbb{R}^k. We define the maximum size of a kk-dimensional corner-free subset of {1,2,⋯ ,N}k\{1,2, \cdots, N\}^k by ck(N)c_k(N). In this paper, we show that the number of kk-dimensional corner-free subsets of the kk-dimensional grid {1,2,⋯ ,N}k\{1,2, \cdots, N\}^k is at most 2O(ck(N))2^{O(c_k(N))} for infinitely many values of NN. Our main tool for the proof is a supersaturation result for kk-dimensional corners in sets of size Θ(ck(N))Θ(c_k(N)) and the hypergraph container method.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.