On the rainbow Cameron-Erdős problem with respect to generalized Sidon sets of multidimensional grids

Abstract

For positive integers $n$, $d$, $k$ and $h$, let $[n{]}^d$ be the $d$-dimensional grid of order $n$, and we refer to the equation ${\sum }_{i=1}^h{x}_{1,i}=\cdots ={\sum }_{i=1}^h{x}_{k,i}$ as the {\it $B_{k,h}$-equation}, where $x_{1,1},\dots ,x_{1,h},\dots ,x_{k,1},\dots ,x_{k,h}$ are $kh$ points in $[n{]}^d$. In this paper, we study the rainbow Cameron-Erdős problem with respect to the $B_{k,h}$-equation. We obtain the asymptotic number of $r$-colorings of $[n{]}^d$ without rainbow solutions to the $B_{k,h}$-equation, and we show that the typical colorings with this property are $(kh-1)$-colorings. We also prove that among all subsets of $[n{]}^d$, $[n{]}^d$ is the unique subset admitting the maximum number of $r$-colorings without rainbow solutions to the $B_{k,h}$-equation. The case $d=1$ and $k=h=2$ of our result confirms a conjecture on Sidon sets by Lin, Wang and Zhou~[{\it European J. Combin.}, 2022]; the case $d=1$, $k=2$ and $h\ge 2$ of our result partly solves a problem concerning linear equations proposed by Cheng, Jing, Li, Wang and Zhou~[{\it J. Combin. Theory Ser. A}, 2023]; the case $d\ge 2$ and $k=h=2$ corresponds to colorings without rainbow (possibly degenerate) parallelograms, and this geometric perspective might be of independent interest. Our proof combines the hypergraph container method with a stability analysis and a deviation gain argument.

23 pages