Minimal Weight in Union-Closed Families
Let Ω be a finite set and let S P(Ω) be a set system on Ω. For xΩ, we denote by d_S (x) the number of members of S containing x. A long-standing conjecture of Frankl states that if S is union-closed then there is some xΩ with d_S (x)≥ 12|S|. We consider a related question. Define the weight of a family S to be w(S) := _A S |A|. Suppose S is union-closed. How small can w(S) be? Reimer showed w(S) ≥ 12 |S| _2 |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 S: if S separates the points of its domain, then w(S)≥ |Ω|2. This is stronger than Reimer’s Theorem when Ω > |S|_2 |S|. In addition we construct a family of examples showing the combined bound on w(S) is tight except in the region |Ω|=Θ (|S|_2 |S|), where it may be off by a multiplicative factor of 2. Our proof also gives a lower bound on the average degree: if S is a point-separating union-closed family on Ω, then 1|Ω| _x Ω d_S (x) ≥ 12 |S| _2 |S|+ O(1), and this is best possible except for a multiplicative factor of 2. , number=1, journal=The Electronic Journal of Combinatorics, author=Falgas-Ravry, Victor, year=2011, month=Apr., pages=#P95