Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.