Change search
ReferencesLink to record
Permanent link

Direct link
Minimal weight in union-closed families
School of Mathematical Sciences Queen Mary University of London, London E1 4NS, UK.
2011 (English)In: The Electronic Journal of Combinatorics, ISSN 1077-8926, Vol. 18, no 1, P95- p.Article in journal (Refereed) Published
Abstract [en]

Let Omega be a finite set and let S subset of P(Omega) be a set system on Omega. For x is an element of Omega, we denote by d(S)(x) the number of members of S containing x.Along-standing conjecture of Frankl states that if S is union-closed then there is some x is an element of Omega with d(S)(x)>= 1/2|S|. We consider a related question. Define the weight of a family S to be w(S) := A.S|A|.SupposeSisunion-closed. How small can w(S) be? Reimer showed w(S) >= 1/2|S|log(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 Omega of S: if S separates the points of its domain, then w(S) >= ((vertical bar Omega vertical bar)(2)). This is stronger than Reimer's Theorem when |Omega| > root|S|log(2)|S|. In addition we constructa family of examples showing the combined bound on w(S)istightexcept in the region |Omega| = Theta(root|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 on Omega, then 1/ |Omega|Sigma(x is an element of Omega)d(S)(x)>= 1/2 root|S|log(2)|S| broken vertical bar O(1), and this is best possible except for a multiplicative factor of 2.

Place, publisher, year, edition, pages
Electronic Journal of Combinatorics , 2011. Vol. 18, no 1, P95- p.
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-80520OAI: diva2:649983
Available from: 2013-09-19 Created: 2013-09-19 Last updated: 2014-02-14Bibliographically approved

Open Access in DiVA

No full text

Other links

Search in DiVA

By author/editor
Falgas-Ravry, Victor
In the same journal
The Electronic Journal of Combinatorics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 53 hits
ReferencesLink to record
Permanent link

Direct link