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$ Commented 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$ Commented 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
    Commented 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$ Commented 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$ Commented 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
    Commented 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
  • $\begingroup$ The question you pose is that of estimating Turan numbers. See, for instance: mathoverflow.net/questions/184210/…. $\endgroup$
    – Mark Lewko
    Commented Jan 29, 2016 at 4:04
  • $\begingroup$ Taking complements, you want the number of size $n-a$ subsets that cover every $n-b$ subset. This is a "covering design" and is extensively studied. See for example arxiv.org/pdf/math/9502238.pdf . $\endgroup$ Commented Jan 29, 2016 at 8:02
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .