Maximum union-free subfamilies

DOI10.1007/S11856-012-0017-0MaRDI QIDQ375829zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Choongbum Lee, Benny Sudakov

Publication date 1 November 2013

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

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

zbMATH Keywords

size of the largest union-free subfamily

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Factorials, binomial coefficients, combinatorial functions (05A10)

Abstract: An old problem of Moser asks: how large of a union-free subfamily does every family of m sets have? A family of sets is called 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. We show that every family of m sets contains a union-free subfamily of size at least lfloor sqrt{4m+1} floor - 1 and that this bound is tight. This solves Moser's problem and proves a conjecture of ErdH{o}s and Shelah from 1972. More generally, a family of sets is a-union-free if there are no a+1 distinct sets in the family such that one of them is equal to the union of a others. We determine up to an absolute multiplicative constant factor the size of the largest guaranteed a-union-free subfamily of a family of m sets. Our result verifies in a strong form a conjecture of Barat, F"{u}redi, Kantor, Kim and Patkos.

Recommendations

• On the number of union-free families
• Large \(B_d\)-free and union-free subfamilies
• Large \(B_d\)-free and union-free subfamilies
• New bounds for union-free families of sets
• Extremal families containing no two sets and their union

Cites work

• scientific article; zbMATH DE number 3363555 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• A problem of Schur and its generalizations
• Estimates related to sumfree subsets of sets of integers
• Extremal problems for sets forming Boolean algebras and complete partite hypergraphs
• On a Combinatorial Problem of Erdos
• On the average size of the sets in a Sperner family
• Partitioning a power set into union-free classes

Cited in

(9)

• Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs
• Union-free families of sets and equations over fields
• On the number of union-free families
• Spanoids -- an abstraction of spanning structures, and a barrier for LCCs
• scientific article; zbMATH DE number 3394140 (Why is no real title available?)
• scientific article; zbMATH DE number 3342002 (Why is no real title available?)
• Maximum \(\mathcal{H}\)-free subgraphs
• Large \(B_d\)-free and union-free subfamilies
• An upper bound on the sizes of multiset-union-free families

This page was built for publication: Maximum union-free subfamilies

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