Maximum union-free subfamilies
An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? 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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Science + Business Media B.V.
2012
|
| Online Access: | http://hdl.handle.net/1721.1/70972 |
| _version_ | 1826201794253946880 |
|---|---|
| author | Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author_sort | Fox, Jacob |
| collection | MIT |
| description | An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? 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 [[sqrt 4m+1]] - 1 that this bound is tight. This solves Moser’s problem and proves a conjecture of Erdos and Shelah from 1972.
More generally, a family of sets is a-union-free if there are no alpha + 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üredi, Kantor, Kim and Patkos. |
| first_indexed | 2024-09-23T11:57:00Z |
| format | Article |
| id | mit-1721.1/70972 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:57:00Z |
| publishDate | 2012 |
| publisher | Springer Science + Business Media B.V. |
| record_format | dspace |
| spelling | mit-1721.1/709722022-10-01T07:11:33Z Maximum union-free subfamilies Fox, Jacob Lee, Choongbum Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Fox, Jacob An old problem of Moser asks: what is the size of the largest union-free subfamily that one can guarantee in every family of m sets? 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 [[sqrt 4m+1]] - 1 that this bound is tight. This solves Moser’s problem and proves a conjecture of Erdos and Shelah from 1972. More generally, a family of sets is a-union-free if there are no alpha + 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üredi, Kantor, Kim and Patkos. National Science Foundation (U.S.) (NSF grant DMS-1101185) National Science Foundation (U.S.) (NSF-CAREER Award (DMS-0812005) United States-Israel Binational Science Foundation Samsung Scholarship Foundation Simons Foundation National Science Foundation (U.S.) (NSF grant DMS-1069197) 2012-05-31T20:39:57Z 2012-05-31T20:39:57Z 2012-02 2011-01 Article http://purl.org/eprint/type/JournalArticle 0021-2172 1565-8511 http://hdl.handle.net/1721.1/70972 Fox, Jacob, Choongbum Lee, and Benny Sudakov. “Maximum Union-free Subfamilies.” Israel Journal of Mathematics (2012): 1-13. Web. en_US http://dx.doi.org/10.1007/s11856-012-0017-0 Israel Journal of Mathematics Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Science + Business Media B.V. MIT web domain |
| spellingShingle | Fox, Jacob Lee, Choongbum Sudakov, Benny Maximum union-free subfamilies |
| title | Maximum union-free subfamilies |
| title_full | Maximum union-free subfamilies |
| title_fullStr | Maximum union-free subfamilies |
| title_full_unstemmed | Maximum union-free subfamilies |
| title_short | Maximum union-free subfamilies |
| title_sort | maximum union free subfamilies |
| url | http://hdl.handle.net/1721.1/70972 |
| work_keys_str_mv | AT foxjacob maximumunionfreesubfamilies AT leechoongbum maximumunionfreesubfamilies AT sudakovbenny maximumunionfreesubfamilies |