<p>I am not sure if these results are known. If you define the $t$-thick upper (or lower, does not matter) shadow of $A_k$ as the sets of one level higher (resp. lower) that contain (resp. are contained in) at least $t$ sets from $A_k$, then what you ask for is the $(k+1)/2$-thick upper shadow. As far as I know it is open to determine the size of the smallest $A_k$ whose $2$-thick shadow is empty. Unfortunately I cannot point you to a reference but I think I heard it from Katona. (And in case I am wrong, then I remember incorrectly...)</p>

CC BY-SA 3.0
2013-11-22T22:32:27.257Z
Thanks for the answer. So it seems like the question is probably too hard to compute exactly what the minimizing set is. But do you think one can argue something in this spirit.

Suppose the density of $A_k$ is some constant (bounded away from 0 and 1). Can we say the density of the $(k+1)/2$ thick upper shadow is at least some constant fraction lesser. At this point of time I cannot even convince myself that the density necessarily reduces. Is there a simple possible counterexample to this ?
NAg
CC BY-SA 3.0
2013-11-23T10:04:52.907Z
What is your definition of density? If $k=1$ and $|A_1|=n/2$, then $M_u(A_1)|$ is about $3/4{n \choose 2}$, so the density increases.
domotorp
CC BY-SA 3.0
2013-11-23T16:09:06.133Z
My definition of density is $\frac{|A_k|}{\binom{n}{k}}$. The example that you gave indeed shows that the density increases but can we up with such examples for all k. One candidate is take all vertices in $\binom{n}{k}$ but one. The density of $M_u(A_k)$ would be 1 where as the density of $A_k$ < 1. However this has non-constant density.
NAg
CC BY-SA 3.0
2013-11-23T16:09:43.980Z
We can also get a set where the density does not decrease by a constant fraction. Let $A_k$ be the set of strings with $k$ ones in the first n-1 bits. $M_u(A_k)$ is the set of strings with $k+1$ ones in the first n-1 bits. The density decrease is a subtractive $\frac{1}{n-k}$. I am not sure if this is the worst such set.
NAg
CC BY-SA 3.0
2013-11-23T16:47:51.123Z
I just realized that my earlier comment was not what I wanted to say which could have been confusing. In my case I can assume that the density is bounded away from $0$ and $1/2$. This sort of ensures that the sanity check of picking a random $A_k$ is satisfied.
NAg
CC BY-SA 3.0
2013-11-22T09:59:28.707Z
2013-11-22T09:59:28.707Z
domotorp
<p>I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem.</p>

<p>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) </p>

<p>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)$. </p>

<p>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. </p>

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

<p>Thanks in advance</p>

CC BY-SA 3.0
2013-11-22T17:13:56.117Z
some refs on [wikipedia](http://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem)
vzn
<graph-theory><co.combinatorics><set-theory><extremal-combinatorics>
Kruskal-Katona Theorem with Majority?
NAg
# Kruskal-Katona Theorem with Majority?

(Asked by: username_0 on 2013-11-21)

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

**Tags:** graph-theory, co.combinatorics, set-theory, extremal-combinatorics
> **Comments:**
> **username_1**: some refs on [wikipedia](http://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem)  

---

## 1 answers

### Answer by username_2 on 2013-11-22. Score: 3

I am not sure if these results are known. If you define the $t$-thick upper (or lower, does not matter) shadow of $A\_k$ as the sets of one level higher (resp. lower) that contain (resp. are contained in) at least $t$ sets from $A\_k$, then what you ask for is the $(k+1)/2$-thick upper shadow. As far as I know it is open to determine the size of the smallest $A\_k$ whose $2$-thick shadow is empty. Unfortunately I cannot point you to a reference but I think I heard it from Katona. (And in case I am wrong, then I remember incorrectly...)

> **Comments:**
> **username_0**: Thanks for the answer. So it seems like the question is probably too hard to compute exactly what the minimizing set is. But do you think one can argue something in this spirit.  Suppose the density of $A_k$ is some constant (bounded away from 0 and 1). Can we say the density of the $(k+1)/2$ thick upper shadow is at least some constant fraction lesser. At this point of time I cannot even convince myself that the density necessarily reduces. Is there a simple possible counterexample to this ?  
> **username_2**: What is your definition of density? If $k=1$ and $|A_1|=n/2$, then $M_u(A_1)|$ is about $3/4{n \choose 2}$, so the density increases.  
> **username_0**: My definition of density is $\frac{|A_k|}{\binom{n}{k}}$. The example that you gave indeed shows that the density increases but can we up with such examples for all k. One candidate is take all vertices in $\binom{n}{k}$ but one. The density of $M_u(A_k)$ would be 1 where as the density of $A_k$ < 1. However this has non-constant density.  
> **username_0**: We can also get a set where the density does not decrease by a constant fraction. Let $A_k$ be the set of strings with $k$ ones in the first n-1 bits. $M_u(A_k)$ is the set of strings with $k+1$ ones in the first n-1 bits. The density decrease is a subtractive $\frac{1}{n-k}$. I am not sure if this is the worst such set.  
> **username_0**: I just realized that my earlier comment was not what I wanted to say which could have been confusing. In my case I can assume that the density is bounded away from $0$ and $1/2$. This sort of ensures that the sanity check of picking a random $A_k$ is satisfied.  

---

