I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem.

Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has exactly $k$ ones. For any element $x \in \{0,1\}^n$ let $N_l(x)$ be the set of elements obtained by flipping one of the 1's in x to 0. (Generally referred to as the lower shadow of X)

Let the majority upper shadow of $A_k$ referred to as $M_u(A_k)$ be the set such that for each $a \in M_u(A_k)$ number of ones in $a = k+1$ and $|N_l(a) \cap A_k| \geq (\frac{k+1}{2})$. That is more than half of a's neighbours are present in $A_k$. Given the size of $A_k$ can we put an upper bound on the size of $M_u(A_k)$.

Has this problem been studied and are there results are relevant to the above. Note that in case $|A_k| = \binom{n}{k}$ we of course have that $|M_u(A_k)|=\binom{n}{k+1}$. In general I am looking at the size of $A_k$ to be $\epsilon\cdot \binom{n}{k}$ where $\epsilon$ is a small constant.

Could you also refer to me a good survey of the Kruskal-Katona Theorem in general , one that surveys recent results in this setting ?

Thanks in advance


1 Answer 1


One bound you can get is $$\frac{k+1}{2}\vert M_u(A_k)\vert \leq (n - k)\vert A_k\vert$$

This can be seen by double counting the edges between $A_k$ and $M_u(A_k)$: each element of $A_k$ only has $n-k$ edges up, and each element of $M_u(A_k)$ has at least $\frac{k+1}{2}$ edges down.

It's also tight in some cases. For example, say $k$ and $n$ are even, and let $A_k$ be the set of strings with $k/2$ ones among the first $n/2$ bits and $k/2$ ones among the second $n/2$ bits. Then $M_u(A_k)$ is the set of strings with either $(k/2, k/2+1)$ or ($k/2+1, k/2)$ ones among the (first $n/2$, second $n/2)$ bits.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .