Maximum union-free subfamilies
From MaRDI portal
Publication:375829
DOI10.1007/S11856-012-0017-0zbMATH Open1275.05004arXiv1012.3127OpenAlexW2119317325MaRDI QIDQ375829FDOQ375829
Choongbum Lee, Benny Sudakov, Jacob Fox
Publication date: 1 November 2013
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1012.3127
Permutations, words, matrices (05A05) Factorials, binomial coefficients, combinatorial functions (05A10)
Cites Work
- A decomposition theorem for partially ordered sets
- Partitioning a power set into union-free classes
- Estimates related to sumfree subsets of sets of integers
- Extremal problems for sets forming Boolean algebras and complete partite hypergraphs
- On the average size of the sets in a Sperner family
- On a Combinatorial Problem of Erdos
- A problem of Schur and its generalizations
- Title not available (Why is that?)
Cited In (4)
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)
