On the number of union-free families

DOI10.1007/S11856-017-1486-YMaRDI QIDQ2357013zbMATH OpenOpenAlexFDO

Authors József Balogh, Adam Zsolt Wagner

Publication date 7 June 2017

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05)

Abstract: A family of sets is union-free if there are no three distinct sets in the family such that the union of two of the sets is equal to the third set. Kleitman proved that every union-free family has size at most $$. Later, Burosch--Demetrovics-Katona-Kleitman-Sapozhenko asked for the number $alpha(n)$ of such families, and they proved that $$. They conjectured that the constant $2sqrt2$ can be removed in the exponent of the right hand side. We prove their conjecture by formulating a new container-type theorem for rooted hypergraphs.

Recommendations

• Maximum union-free subfamilies
• New bounds for union-free families of sets
• Extremal families containing no two sets and their union
• Large \(B_d\)-free and union-free subfamilies
• Union-closed families

Cites work

• Explicit construction of linear sized tolerant networks
• Extremal properties of collections of subsets containing no two sets and their union
• scientific article; zbMATH DE number 3141308 (Why is no real title available?)
• Hypergraph containers
• Independent sets in hypergraphs
• Kleitman and combinatorics
• On the number of databases and closure operations
• On the Shannon capacity of a graph
• The number of \(C_{2\ell}\)-free graphs

Cited in

(5)

• Union-free families of sets and equations over fields
• New bounds for union-free families of sets
• Large \(B_d\)-free and union-free subfamilies
• Maximum union-free subfamilies
• Lattices and hypergraphs associated to square-free monomial ideals

This page was built for publication: On the number of union-free families

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