Minimal weight in union-closed families

Victor Falgas-Ravry

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

Let $\Omega$ be a finite set and let $\mathcal{S} \subseteq \mathcal{P}(\Omega)$ be a set system on $\Omega$. For $x\in \Omega$, 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 \Omega$ with $d_{\mathcal{S}}(x)\geq \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}) \geq \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 $\Omega$ of $\mathcal{S}$: if $\mathcal{S}$ separates the points of its domain, then $$w(\mathcal{S})\geq \binom{|\Omega|}{2}.$$ This is stronger than Reimer's Theorem when $\vert \Omega \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 $|\Omega|=\Theta (\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 $\Omega$, then $$ \frac{1}{|\Omega|} \sum_{x \in \Omega} d_{\mathcal{S}}(x) \geq \frac{1}{2} \sqrt{|\mathcal{S}| \log_2 |\mathcal{S}|}+ O(1),$$ and this is best possible except for a multiplicative factor of $2$.

Détail

DOI : 10.37236/582

Classification : 05D05