Multicolor Sunflowers
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2015
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916585808068608 |
|---|---|
| author | Mubayi, Dhruv Wang, Lujia |
| author_facet | Mubayi, Dhruv Wang, Lujia |
| contents | A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection $C$ of all of them, and $|C|$ is smaller than each of the sets. A longstanding conjecture due to Erdős and Szemerédi states that the maximum size of a family of subsets of $[n]$ that contains no sunflower of fixed size $k>2$ is exponentially smaller than $2^n$ as $n\rightarrow\infty$. We consider this problem for multiple families. In particular, we obtain sharp or almost sharp bounds on the sum and product of $k$ families of subsets of $[n]$ that together contain no sunflower of size $k$ with one set from each family. For the sum, we prove that the maximum is $$(k-1)2^n+1+\sum_{s=n-k+2}^{n}\binom{n}{s}$$ for all $n \ge k \ge 3$, and for the $k=3$ case of the product, we prove that it is between $$\left(\frac{1}{8}+o(1)\right)2^{3n}\qquad \hbox{and} \qquad (0.13075+o(1))2^{3n}.$$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1512_00525 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Multicolor Sunflowers Mubayi, Dhruv Wang, Lujia Combinatorics A sunflower is a collection of distinct sets such that the intersection of any two of them is the same as the common intersection $C$ of all of them, and $|C|$ is smaller than each of the sets. A longstanding conjecture due to Erdős and Szemerédi states that the maximum size of a family of subsets of $[n]$ that contains no sunflower of fixed size $k>2$ is exponentially smaller than $2^n$ as $n\rightarrow\infty$. We consider this problem for multiple families. In particular, we obtain sharp or almost sharp bounds on the sum and product of $k$ families of subsets of $[n]$ that together contain no sunflower of size $k$ with one set from each family. For the sum, we prove that the maximum is $$(k-1)2^n+1+\sum_{s=n-k+2}^{n}\binom{n}{s}$$ for all $n \ge k \ge 3$, and for the $k=3$ case of the product, we prove that it is between $$\left(\frac{1}{8}+o(1)\right)2^{3n}\qquad \hbox{and} \qquad (0.13075+o(1))2^{3n}.$$ |
| title | Multicolor Sunflowers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1512.00525 |