Reasonable Bounds for Combinatorial Lines of Length Three
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917845413134336 |
|---|---|
| author | Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor |
| author_facet | Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor |
| contents | We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log\log\log\log n)^{-c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, with $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for all $i = 1, 2, \dots, n$. This improves on the previous best bound of $3^{-n}|A| \ge Ω((\log^* n)^{-1/2})$ of [D.H.J. Polymath, Ann. of Math. 2012]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15137 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reasonable Bounds for Combinatorial Lines of Length Three Bhangale, Amey Khot, Subhash Liu, Yang P. Minzer, Dor Combinatorics Computational Complexity We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log\log\log\log n)^{-c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, with $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for all $i = 1, 2, \dots, n$. This improves on the previous best bound of $3^{-n}|A| \ge Ω((\log^* n)^{-1/2})$ of [D.H.J. Polymath, Ann. of Math. 2012]. |
| title | Reasonable Bounds for Combinatorial Lines of Length Three |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2411.15137 |