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

Improve this question
$\endgroup$
1
  • $\begingroup$ some refs on wikipedia $\endgroup$
    – vzn
    Nov 22, 2013 at 17:13

1 Answer 1

Reset to default
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...)

Improve this answer
$\endgroup$
5
  • $\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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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