Collection of subsets with adding one element property

209 Views Asked by At

Let $\mathcal{F}$ be a collection of subsets of $\{1,2,\ldots,n\}$ such that for any set $A\in\mathcal{F}$, there exists $B\not\in \mathcal{F}$ such that $A\subset B\subseteq\{1,2,\ldots,n\}$ and $|B|=|A|+1$. What is the maximum size of $\mathcal{F}$?

One bound is that $\mathcal{F}$ can be of size at least $2^{n-1}$. Indeed, if $n$ is even, put all subsets of odd size in $\mathcal{F}$ (and vice versa if $n$ is odd.) And of course $\mathcal{F}$ is of size no more than $2^n$, the number of subsets of $\{1,2,\ldots,n\}$.

Any better upper/lower bounds?

1

There are 1 best solutions below

4
On BEST ANSWER

My guess for the correct answer is $(1-\Theta(1/n)) 2^n$, though I can't quite show that.

Here is a probabilistic construction that gives $(1-O(\log n/n))2^n$. The $\log n$ can probably be removed. Let $0 \leq w < n$. Choose some probability $p$, and put each $x \in \binom{n}{w+1}$ in a set $S_{w+1}$ with probability $p$. The probability that some $y \in \binom{n}{w}$ doesn't get covered by some set in $S_{w+1}$ is $(1-p)^{n-w}$, and we put all these into some set $T_w$. We will later throw away both $S_{w+1}$ and $T_w$. The expected size of both sets together is $p\binom{n}{w+1} + (1-p)^{n-w} \binom{n}{w}$, and there is some choice achieving this. Choosing $p = \log(n-w)/(n-w)$, we get $(1-p)^{n-w} \approx 1/(n-w) < p$. When $w \leq (1-\epsilon) n$ (for some arbitrary constant $0 < \epsilon < 1/2$), $p \leq \log n/(\epsilon n)$. Hence by taking all sets of weight at most $(1-\epsilon) n$ and removing all $T_w$ and $S_{w+1}$, we get a set satisfying your property whose density is $1-\log n/(\epsilon n)$. (The total weight of sets of weight more than $(1-\epsilon) n$ is exponentially small.)

In order to remove the $\log n$, we can try to intelligently choose $S_{w+1}$. The calculation below shows that in order to obtain $T_w = \emptyset$ we need $|S_{w+1}| \geq 1/(n-w) \binom{n}{w+1}$, and I imagine that there is a construction almost achieving this. Such a construction would give a family of size $(1-O(1/n))2^n$.

Here is an upper bound of $(1-\Omega(1/n))2^n$. Given a family $\mathcal{F}$, let $S_w = \mathcal{F} \cap \binom{n}{w}$ belongs to the family. Since each set in $\binom{n}{w+1}$ covers at most $w+1$ sets in $S_w$, at least $|S_w|/(w+1)$ sets must be omitted from the family. If $|S_w| = \alpha \binom{n}{w}$ then $$ \frac{|S_w|}{w+1} = \frac{\alpha}{n-w} \binom{n}{w+1}. $$ Hence for $w < (1-\epsilon)n$ (for some arbitrary constant $0 < \epsilon < 1/2$), either $|S_w| < (1/2) \binom{n}{w}$ or $|S_{w+1}| < (1-1/(2\epsilon n)) \binom{n}{w+1}$ (we could choose a better cutoff instead of $1/2$ to get better constants). In total, again using the fact that large sets are an exponentially small fraction of all sets, we get that $|\mathcal{F}| \leq (1-\Omega(1/n))2^n$.