I learned that the average size in any ideal of subsets of $[n]$ is at most $n/2$, but I think the downward closed family of the subsets of $[n]$ also satisfied. I want to know how to proof it or it is wrong. A downward closed family $\mathcal{F}$ means for any $A \in \mathcal{F}, B \subseteq A$, we have $B \in \mathcal{F}$, and the ideal's definition is here https://en.wikipedia.org/wiki/Ideal_(set_theory).
6
-
2$\begingroup$ Didn't you ask this question already? Why did you delete it and re-ask it again using a different account? $\endgroup$– Emil JeřábekCommented Jun 10, 2020 at 12:55
-
$\begingroup$ Someone posted an irrelevant discussion under the question before, maybe I should deal with it in other ways. $\endgroup$– CynastyCommented Jun 10, 2020 at 13:31
-
2$\begingroup$ Please, in the future, do not repost questions in this way. In the uncommon case that someone posts a spam answer like that again, do not worry about it, it will be dealt with soon. (Note that the offending post was being heavily downvoted and, apparently, attracted spam flags. Most likely it would get deleted in short order.) $\endgroup$– Emil JeřábekCommented Jun 10, 2020 at 13:44
-
2$\begingroup$ @Seva I think the question is not about the average size of downsets, but about the average size of sets inside any downset. $\endgroup$– Emil JeřábekCommented Jun 10, 2020 at 19:34
-
1$\begingroup$ I think @EmilJeřábek is right about the intended meaning. (The alternative, the average size of downsets, is $2^{n-1}$ for symmetry reasons.) $\endgroup$– Andreas BlassCommented Jun 11, 2020 at 2:37
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
Here is a pedestrian answer. If $\def\cF{\mathcal F}\cF$ is a downward closed subset of $\mathcal P([n])$, we have
$$\frac1{|\cF|}\sum_{A\in\cF}|A|=\sum_{i\in[n]}\Pr_{A\in\cF}[i\in A].$$
Now, for any $i\in[n]$,
$$\Pr_{A\in\cF}[i\in A]\le\frac12,$$
because the mapping $A\mapsto A\smallsetminus\{i\}$ provides an injection
$$\{A\in\cF:i\in A\}\to\{A\in\cF:i\notin A\}.$$
answered Jun 10, 2020 at 22:40
$\begingroup$
$\endgroup$
This is true and indeed, much more can be said: if $\mathcal F$ is a downward closed family of subsets of $[n]$, then $$ \frac1{|\mathcal F|}\, \sum_{F\in\mathcal F} |F| \le \frac12\, \log_2|\mathcal F|; $$ equivalently, if $A\subseteq\{0,1\}^n$ is a downset, then $$ \frac1{|A|}\, \sum_{a\in A} w(a) \le \frac12\, \log_2 |A|, $$ where $w(a)$ is the number of non-zero components of $a$. This is Theorem 3 of the linked paper (see also the abstract).
