umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Minimal weight in union-closed families
School of Mathematical Sciences Queen Mary University of London, London E1 4NS, UK.
2011 (Engelska)Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, nr 1, s. P95-Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Electronic Journal of Combinatorics , 2011. Vol. 18, nr 1, s. P95-
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-80520OAI: oai:DiVA.org:umu-80520DiVA, id: diva2:649983
Tillgänglig från: 2013-09-19 Skapad: 2013-09-19 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

http://www.emis.ams.org/journals/EJC/Volume_18/PDF/v18i1p95.pdfhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p95

Personposter BETA

Falgas-Ravry, Victor

Sök vidare i DiVA

Av författaren/redaktören
Falgas-Ravry, Victor
I samma tidskrift
The Electronic Journal of Combinatorics
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 165 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf