Maximum union-free subfamilies

Details Maximum union-free subfamilies Maximum union-free subfamilies

2010-12-14

arxiv.org/abs/1012.3127v6

Mathematics

Combinatorics

10 pages

Scientific paper

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}\rfloor - 1 and that this bound is tight. This solves Moser's problem and proves a conjecture of Erd\H{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.

Affiliated with

Also associated with

No associations

Rating

Maximum union-free subfamilies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximum union-free subfamilies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum union-free subfamilies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180261