Estimating the number of edges in a subset-poset in terms of the total number of elements

Question

Let $S$ be a finite set of sets, with $N = \sum_{s \in S} |s|$ the 'total cardinality' of $S$; i.e., the sum of the cardinalities of all the sets in $S$. Now, consider the poset $(S, \subset)$ of $S$ partially ordered by the subset relation. I want to estimate the 'edge size' of this poset (that is, $|\subset|$, the number of pairs in the subset relation or the number of edges in the subset DAG) in terms of the total cardinality $N$. There is an obvious bound of $O(N^2)$ (since $|S|\leq N$ and $|\subset|\in O(|S|^2)$), but is it possible to do any better than this, possibly even to prove a linear $O(N)$ bound on $|\subset|$?

Answer 1

The answer can be $\Omega(N^{2-\epsilon})$ for any epsilon.Consider the 'universe' $U=\{1, 2, \ldots, n\}$, fix some number $k$, and let $S$ be all the subsets $U$ of size either $k$ or $n-k$. Then there are $n\choose k$ sets in $S$ of size $k$ and ${n\choose n-k }={n\choose k}$ sets of size $n-k$, so $N=\sum_{s\in S}|s| = n\cdot {n\choose k}\approx C_0n^{k+1}$ for some constant $C_0$ (dependent on $k$ but not $n$). Meanwhile, for each of the sets of size $n-k$ it has ${n-k\choose k}$ subsets of size $k$, so $|\subset| = {n\choose k}\cdot {n-k\choose k}\approx C_1(n-k)^k\cdot n^k\approx C_2 n^{2k}$ (again, with constants dependent on $k$ but not $n$). This, in turn, is proportional to $\left(n^{k+1}\right)^{2k/(k+1)} = N^{2k/(k+1)} = N^{2-2/(k+1)}$, and so by choosing $k$ large enough (and then $n$ much larger, of course) we can best any $N^{2-\epsilon}$.

By letting $k$ vary as a function of $n$, say $k\in\Theta(\log n)$, this can probably go all the way to $\Omega(N^2\log^{-p}N)$ for some $p$, but I'm not sure what the best $p$ you could get from this approach is, or whether it can in fact be taken all the way to $\Theta(N^2)$.