A stability result for the union-closed size problem

DOI10.1017/S0963548315000176zbMATH Open1372.05016arXiv1311.2298OpenAlexW3103079811MaRDI QIDQ5366897FDOQ5366897

Authors: Tom Eccles 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: A family of sets is called union-closed if whenever $A$ and $B$ are sets of the family, so is $AcupB$. The long-standing union-closed conjecture states that if a family of subsets of $[n]$ is union-closed, some element appears in at least half the sets of the family. A natural weakening is that the union-closed conjecture holds for large families; that is, families consisting of at least $p_0{2}^n$ sets for some constant $p_0$. The first result in this direction appears in a recent paper of Balla, Bollob'as and Eccles cite{BaBoEc}, who showed that union-closed families of at least $frac232^n$ sets satisfy the conjecture --- they proved this by determining the minimum possible average size of a set in a union-closed family of given size. However, the methods used in that paper cannot prove a better constant than $frac23$. Here, we provide a stability result for the main theorem of cite{BaBoEc}, and as a consequence we prove the union-closed conjecture for families of at least $(frac23-c)2^n$ sets, for a positive constant $c$.

Full work available at URL: https://arxiv.org/abs/1311.2298

Recommendations

• Union-closed families of sets
• Note on the union-closed sets conjecture
• Publication:4204156
• Union-closed families
• scientific article; zbMATH DE number 729129

Mathematics Subject Classification ID

Partitions of sets (05A18) Extremal set theory (05D05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Compressions and isoperimetric inequalities
• On the scope of averaging for Frankl's conjecture
• An Average Set Size Theorem
• Union-closed families of sets

Cited In (5)

• New conjectures for union-closed families
• Union-closed families of sets
• Union-closed families with small average overlap densities
• Well-graded families and the union-closed sets conjecture
• Random union-closed families

This page was built for publication: A stability result for the union-closed size problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366897)