A stability result for the union-closed size problem

DOI10.1017/S0963548315000176MaRDI QIDQ5366897zbMATH OpenOpenAlexFDO

Authors Tom Eccles

Publication date 10 October 2017

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

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

Mathematics Subject Classification ID

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

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$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• An Average Set Size Theorem
• Compressions and isoperimetric inequalities
• On the scope of averaging for Frankl's conjecture
• 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)