A grid generalisation of the Kruskal-Katona theorem

2019/08/06 by Raty, Eero
#05D05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.02253

Abstract

For a set A⊆[k]ⁿ=\ 0,…,k-1\ ⁿ, we define the d-shadow of A to be the set of points obtained by flipping to zero one of the non-zero coordinates of some point in A. Let [k]_rⁿ be the set of those points in [k]ⁿ with exactly r non-zero coordinates. Given the size of A, how should we choose A⊆[k]_rⁿ 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 [t]_rⁿ are extremal for every t. We also give an exact answer to the 'unrestricted' question when we just have A⊆[k]ⁿ, showing for example that the set of points with at least r zeroes is extremal for every r.

Related

• Extremal families for the Kruskal--Katona theorem
• Coordinate deletion of zeroes
• Tight bounds for Katona's shadow intersection theorem
• Multidimensional Kruskal-Katona theorem
• Shadows of 3-uniform hypergraphs under a minimum degree condition