EKR Sets for Large n and r
Let A⊂([n]r) be a compressed, intersecting family and let X⊂[n]. Let A(X)={A∈A:A∩X≠∅} and Sn,r=([n]r)({1}). Motivated by the Erdős–Ko–Rado theorem, Borg asked for which X⊂[2,n] do we have |A(X)|≤|Sn,r(X)| for all compressed, intersecting families A? We call X that satisfy this property EKR. Borg cla...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Japan
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110210 |
| _version_ | 1811078035851444224 |
|---|---|
| author | Bond, Benjamin Bond, Benjamin R. |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Bond, Benjamin Bond, Benjamin R. |
| author_sort | Bond, Benjamin |
| collection | MIT |
| description | Let A⊂([n]r) be a compressed, intersecting family and let X⊂[n]. Let A(X)={A∈A:A∩X≠∅} and Sn,r=([n]r)({1}). Motivated by the Erdős–Ko–Rado theorem, Borg asked for which X⊂[2,n] do we have |A(X)|≤|Sn,r(X)| for all compressed, intersecting families A? We call X that satisfy this property EKR. Borg classified EKR sets X such that |X|≥r. Barber classified X, with |X|≤r, such that X is EKR for sufficiently large n, and asked how large n must be. We prove n is sufficiently large when n grows quadratically in r. In the case where A has a maximal element, we sharpen this bound to n>φ2r implies |A(X)|≤|Sn,r(X)|. We conclude by giving a generating function that speeds up computation of |A(X)| in comparison with the naïve methods. |
| first_indexed | 2024-09-23T10:52:21Z |
| format | Article |
| id | mit-1721.1/110210 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:52:21Z |
| publishDate | 2017 |
| publisher | Springer Japan |
| record_format | dspace |
| spelling | mit-1721.1/1102102022-09-30T23:36:48Z EKR Sets for Large n and r Bond, Benjamin Bond, Benjamin R. Massachusetts Institute of Technology. Department of Mathematics Bond, Benjamin R. Let A⊂([n]r) be a compressed, intersecting family and let X⊂[n]. Let A(X)={A∈A:A∩X≠∅} and Sn,r=([n]r)({1}). Motivated by the Erdős–Ko–Rado theorem, Borg asked for which X⊂[2,n] do we have |A(X)|≤|Sn,r(X)| for all compressed, intersecting families A? We call X that satisfy this property EKR. Borg classified EKR sets X such that |X|≥r. Barber classified X, with |X|≤r, such that X is EKR for sufficiently large n, and asked how large n must be. We prove n is sufficiently large when n grows quadratically in r. In the case where A has a maximal element, we sharpen this bound to n>φ2r implies |A(X)|≤|Sn,r(X)|. We conclude by giving a generating function that speeds up computation of |A(X)| in comparison with the naïve methods. National Science Foundation (U.S.) (Grant No. 1062709) United States. Department of Defense (Grant No. 1062709) United States. National Security Agency (Grant Number H98230-11-1-0224) 2017-06-23T15:37:50Z 2017-06-23T15:37:50Z 2015-08 2014-04 2016-05-23T12:08:48Z Article http://purl.org/eprint/type/JournalArticle 0911-0119 1435-5914 http://hdl.handle.net/1721.1/110210 Bond, Benjamin. "EKR Sets for Large n and r." Graphs and Combinatorics (2016) 32: 495-510. en http://dx.doi.org/10.1007/s00373-015-1602-x Graphs and Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer Japan application/pdf Springer Japan Springer Japan |
| spellingShingle | Bond, Benjamin Bond, Benjamin R. EKR Sets for Large n and r |
| title | EKR Sets for Large n and r |
| title_full | EKR Sets for Large n and r |
| title_fullStr | EKR Sets for Large n and r |
| title_full_unstemmed | EKR Sets for Large n and r |
| title_short | EKR Sets for Large n and r |
| title_sort | ekr sets for large n and r |
| url | http://hdl.handle.net/1721.1/110210 |
| work_keys_str_mv | AT bondbenjamin ekrsetsforlargenandr AT bondbenjaminr ekrsetsforlargenandr |