A grid generalisation of the Kruskal-Katona theorem
2019
For a set $A\subseteq\left[k\right]^{n}=\left\{ 0,\dots,k-1\right\} ^{n}$, we define the $d$-shadow to be the set obtained from any point of $A$ by flipping a non-zero coordinate to zero. Let $\left[k\right]_{r}^{n}$ be the set of those points in $\left[k\right]^{n}$ with exactly $r$ non-zero coordinates. For given $\left|A\right|$, how should we choose $A\subseteq\left[k\right]_{r}^{n}$ so as to minimise the $d$-shadow? Note that the case $k=2$ is answered by the Kruskal-Katona theorem.
Our aim in this paper is to give an exact answer to this question. In particular, we show that the sets $\left[t\right]_{r}^{n}$ are extremal for every $t$. We also give an exact answer to the 'unrestricted' question when we just have $A\subseteq\left[k\right]^{n}$, showing for example that the set of points with at least $r$ zeroes is extremal for every $r$.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
5
References
0
Citations
NaN
KQI