5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ some refs on wikipedia $\endgroup$ – vzn Nov 22 '13 at 17:13
3
$\begingroup$

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...)

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – NAg Nov 22 '13 at 22:32
  • $\begingroup$ 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. $\endgroup$ – domotorp Nov 23 '13 at 10:04
  • $\begingroup$ 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. $\endgroup$ – NAg Nov 23 '13 at 16:09
  • $\begingroup$ 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. $\endgroup$ – NAg Nov 23 '13 at 16:09
  • $\begingroup$ 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. $\endgroup$ – NAg Nov 23 '13 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.