Minimal weight in union-closed families

Details Minimal weight in union-closed families Minimal weight in union-closed families

2011-01-13

arxiv.org/abs/1101.2589v1

Mathematics

Combinatorics

16 pages

Scientific paper

Let Omega be a finite set and let S be a set system on Omega. For x in Omega, 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 d(x) \geq |S|/2 for some x in Omega. We consider a related question. Define the weight of S to be w(S)= \sum_{A in S} |A|. Suppose S is union-closed. How small can w(S) be? Reimer showed that w(S) \geq |S| \log_{2} |S| /2, and that this inequality is sharp. In this paper we show how his bound may be improved if we have some additional information about the domain Omega of S: if S separates the points of Omega, then w(S) \geq \binom{|\Omega|}{2}. This is stronger than Reimer's Theorem when Omega > \sqrt{|S|\log_2 |S|}. In addition we construct a family of examples showing the combined bound on w(S) is tight except in the region |\Omega|=\Theta (\sqrt{|S|\log_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, then the average degree over its domain is at least 1/2 \sqrt{|S| \log_2 |S|}+ O(1), and this is best possible except for a multiplicative factor of 2.

Affiliated with

Also associated with

No associations

Rating

Minimal weight in union-closed families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal weight in union-closed families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal weight in union-closed families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66794