3
$\begingroup$

Fix $1>c>0$. Consider the set $[n]=\{1,2,\ldots,n\}$ and the set of all subsets of this set which we'll denote as $2^{[n]}$. Let $S \subseteq 2^{[n]}$ be a set system such that for every non-empty set $A \in 2^{[n]}$ there exists a set $A' \in S$ such that $A' \subseteq A$ and $|A'| > c |A|$. How small can $|S|$ be?

Added: The "obvious" construction of such a set system $S$ is obtained by taking all subsets of size at most $cn$. For $c<1/2$, this gives $$|S| = \sum_{i=1}^{cn} \pmatrix{n \\ i}= 2^{nH(c)-\log_2(n)/2 +O(1)}$$ where $H(c)=c\log_2(1/c)+(1-c) \log_2(1/(1-c)).$

Can we do better?

$\endgroup$
6
  • $\begingroup$ Surely you need to exclude $A=\varnothing$.... $\endgroup$ Jan 28, 2016 at 19:05
  • 1
    $\begingroup$ Excluding $A=\varnothing$, $S$ can have $n$ elements: take $S$ to be the set of all singletons, and take $c=n+1$. On the other hand, $S$ must contain all singletons, since taking $A$ to be a singleton forces $A'$ to be a singleton. So $S$ must have at least $n$ elements. $\endgroup$ Jan 28, 2016 at 19:07
  • $\begingroup$ @Arturo, I'm mostly interested in the case when $1>c>0$ is fixed and $n$ is large. $\endgroup$
    – Mark Lewko
    Jan 28, 2016 at 19:10
  • $\begingroup$ Got it; (it should have been $c=1/(n+1)$, but I see that you want $c$ fixed and independent of $n$). $\endgroup$ Jan 28, 2016 at 19:23
  • 1
    $\begingroup$ I'll assume that you allow $|A'|=c|A|$. As far as the "obvious construction" of all sets with size at most $s_1=\lceil cn \rceil,$ couldn't one iterate and take just all sets with sizes from the list $s_1,s_2,\cdots s_k=1$ where $s_1$ is as before and $s_{i+1}=\lceil cs_i \rceil$ So for $n=100$ and $c=1/3$ rather than the proposed all sets of size at most $34$, it would suffice to take just those of sizes $34,12,4,2,1.$ $\endgroup$ Jan 28, 2016 at 22:42

4 Answers 4

2
$\begingroup$

I assume that $c$ is small. Then the minimal answer $(A_n)^{cn}$, where $\sqrt{2}\leqslant \liminf A_n\leqslant e^{1/e}$.

Lower bound. Fix $\varepsilon>0$. We prove that for large $n$ each set $A'$ serves for at most $2^{n-cn/2}$ sets $A$ such that $|A|\geqslant n/2$. Indeed, such $A'$ must have size at least $|A'|\geqslant c|A|\geqslant (c/2)n$, therefore there exist at most $2^{n-cn/2}$ oversets of $A'$. Thus we need at least $$ 2^{n-1}/2^{n-cn/2}=2^{cn/2-1} $$ different sets $A'$.

Upper bound. For each given positive integer $k=\alpha n$, with $\alpha \leqslant c$, fix some $p\in (0,1)$ and choose each set of size $k$ with probability $p$. What is the probability that some set $A$, $|A|=k/c$ (well, I omit integer parts and so on), does not have any chosen subset of size $k$? It equals $$ (1-p)^{\binom{k/c}{k}}\leqslant e^{-p\binom{k/c}{k}}\leqslant e^{-p\cdot \exp(n\cdot \alpha H(c)/c)}, $$ where $H(t)=-t\log t-(1-t)\log(1-t)$ is entropy function and I use the well-known bound $\binom{N}{cN}\leqslant e^{H(c)N}$. That is why we naturally take $p=n\exp(-n\cdot \alpha H(c)/c)$. Then the probability that $A$ has no chosen subset is at most $e^{-n}$, and even if we sum up by all possible $A$ we still get at most $(2/e)^n$. How many subsets do we choose? Expectation is $$E:= p\binom{n}{\alpha n}\leqslant p\cdot e^{n\cdot H(\alpha)}=n\exp\left(n\cdot(H(\alpha)-\alpha H(c)/c)\right). $$ We have $H(c)=-c\log c+c+O(c^2)$ for small $c$. It follows that $$ H(\alpha)-\alpha H(c)/c=c\cdot \frac\alpha{c}\cdot \log\frac{c}\alpha+O(c^2)\leqslant c/e+O(c^2), $$ since $x^{-1}\log x\leqslant 1/e$ for $x=c/\alpha\geqslant 1$. It remains to apply some standard estimate for large deviation from the expectation (Markov inequality is enough) and sum up by all $k$.

This bound $e^{O(cn)}$ is better for small $c$ than $e^{H(c)\cdot n}$ proved by taking all sets of size at most $cn$.

$\endgroup$
1
  • 1
    $\begingroup$ Yes. I am looking for the precise form / asymptotic of the lower bound as a function of c. $\endgroup$
    – Mark Lewko
    Jan 28, 2016 at 19:28
0
$\begingroup$

While we don't know the right exponential function we can ignore linear factors. So we might as well ask the question:

How many sets of size $a$ does it take to get a subset of every set of size $b$? Then we can sum over $b$ every number between $1$ and $n$ and $a= \lfloor cb \rfloor +1$.

The most naive upper bound bound is $\binom{n}{a}$ and the most naive lower bound is $\binom{n}{a}/ \binom{b}{a}$ by the counting argument. (If you take every set of size $a$ then every set of size $b$ is counted $\binom{b}{a}$ times, so you can't save more than that.)

Brendan's upper bound is $\binom{n-b+a}{a}$. This represents a savings of $\binom{n}{a}/\binom{n-b+a}{a}$. As $b$ approaches $n$ this approaches the upper bound but when $b$ is small this is from from it.

I haven't calculated Fedor's lower bound in this framework.

$\endgroup$
2
0
$\begingroup$

An improvement on the "obvious upper bound" is to take all $k$-subsets of $\lbrace 1,\ldots,n-k/c+k\rbrace$ for $k=1,\ldots,cn$. This ensures that for each $A\subseteq [n]$ the lexicographically least $c|A|$-subset is present. I think it is better by an exponential amount.

$\endgroup$
0
$\begingroup$

Let $b=\lceil \frac1c \rceil$ , color the $n$ elements as evenly as possible with $b$ colors and then take the monochromatic subsets. I can believe that probabilistic methods outshine that. However, in a few cases I looked at, this does better than other simple explicit constructions. For example with $n=100$ and $c=1/3$ this would use $2^{33}+2^{33}+2^{34}-3=2^{35}-3$ subsets.

$\endgroup$

Your Answer

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

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