Forbidden stars in multidimensional $0$-$1$ matrices and visibility of lattice points

Abstract

A $d$-dimensional $0$-$1$ matrix $M$ of size $n_1\times n_2\times \cdots \times n_d$ can be considered as a Boolean function $M:B(n_1\times n_2\times \cdots \times n_d)\to \{0,1\}$, where $B$ is the $d$-dimensional box of lattice points $(x_1,\dots ,,x_d)\in Z^d$ with $0\le x_i\le n_i-1$, $1\le i\le d$. The $0$-$1$ matrix $M$ can also be described as a subset $P:=P(M)$ of $B$ such that $x\in P$ if and only if $M(x)=1$. A $k$-star with center $p$ in $M$ corresponds to a $(k+1)$-element subset $\{p,p_1,\dots ,p_k\}\subset B$ such that $p$ and $p_i$ differ only in one coordinate (for all $1\le i\le k$) and these $k$ coordinates are distinct. Here we consider the problem of determining the maximum number of $1$-entries of a $0$-$1$ matrix $M$ of dimension $d$ and size $n\times n\times \cdots \times n$ that avoids all $k$-stars. Our main results are the asymptotical solution of the problem for every $d$ and $k$ (as $n\to \infty$), very close bounds for $k=d$, and the exact solution of the $d=k=3$ case. This problem has connections to several other areas of discrete mathematics, including $k$-partite hypergraphs, independent set problems, dominating set problems and covering codes. One of our tools (concerning maximal packings of induced copies of a given hypergraph) might have independent interest.