Summary: 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{1\over 2}|{\mathcal S}|\). [\textit{P. Frankl}, ``Extremal set system, Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland). 1293-1329 (1995; Zbl 0844.05094)] 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{1\over 2}|{\mathcal S}|\log_2 |{\mathcal S}|, \] and that this inequality is tight [\textit{D. Reimer}, ``An average set size theorem, Comb. Probab. Comput. 12, No.\,1, 89--93 (2003; Zbl 1013.05083)]. 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 {|\Omega|\choose 2}. \] This is stronger than Reimer's Theorem when \(|\Omega|> \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 \[ {1\over|\Omega|} \sum_{x\in\Omega} d_{{\mathcal S}}(x)\geq{1\over 2}\sqrt{|{\mathcal S}|\log_2|{\mathcal S}|}+ O(1), \] and this is best possible except for a multiplicative factor of 2.
- Stability of characters and filters for weighted semilattices
- Extremal union-closed set families
- Minimizing the weight of the union-closure of uniform families of sets
- New conjectures for union-closed families
- Minimizing the weight of the union-closure of families of two-sets
- The union-closed sets conjecture for small families
- The journey of the union-closed sets conjecture
This page was built for publication: Minimal weight in union-closed families
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540093)
