Minimal Weight in Union-Closed Families - Falgas-Ravry, Victor (The Electronic Journal of Combinatorics, 2011)
Let $Ω$ be a finite set and let $\mathcal{S} \subseteq \mathcal{P}(Ω)$ be a set system on $Ω$. For $x\in Ω$, we denote by $d_{\mathcal{S}}(x)$ the number of members of $\mathcal{S}$ containing $x$. A long-standing conjecture of Frankl states that if $\mathcal{S}$ is union-closed then there is some $x\in Ω$ with $d_{\mathcal{S}}(x)≥ \frac{1}{2}|\mathcal{S}|$. We consider a related question. Define the weight of a family $\mathcal{S}$ to be $w(\mathcal{S}) := \sum_{A \in \mathcal{S}} |A|$. Suppose $\mathcal{S}$ is union-closed. How small can $w(\mathcal{S})$ be? Reimer showed $$w(\mathcal{S}) ≥ \frac{1}{2} |\mathcal{S}| \log_2 |\mathcal{S}|,$$ and that this inequality is tight. In this paper we show how Reimer's bound may be improved if we have some additional information about the domain $Ω$ of $\mathcal{S}$: if $\mathcal{S}$ separates the points of its domain, then $$w(\mathcal{S})≥ \binom{|Ω|}{2}.$$ This is stronger than Reimer's Theorem when $\vert Ω \vert > \sqrt{|\mathcal{S}|\log_2 |\mathcal{S}|}$. In addition we construct a family of examples showing the combined bound on $w(\mathcal{S})$ is tight except in the region $|Ω|=Θ (\sqrt{|\mathcal{S}|\log_2 |\mathcal{S}|})$, where it may be off by a multiplicative factor of $2$. Our proof also gives a lower bound on the average degree: if $\mathcal{S}$ is a point-separating union-closed family on $Ω$, then $$ \frac{1}{|Ω|} \sum_{x \in Ω} d_{\mathcal{S}}(x) ≥ \frac{1}{2} \sqrt{|\mathcal{S}| \log_2 |\mathcal{S}|}+ O(1),$$ and this is best possible except for a multiplicative factor of $2$.