2023-08-28
Raising the roof on the threshold for Szemerédi‘s theorem with random differences
Publication
Publication
Presented at the
12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 (August 2023), Prague, Czech Republic
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi’s theorem with random differences is bounded from above by N 1 − 2 k + o (1) for length- k progressions. This improves the previous best bounds of N 1 − 1 d k/ 2 e + o (1) for all odd k.
| Additional Metadata | |
|---|---|
| doi.org/10.5817/CZ.MUNI.EUROCOMB23-032 | |
| Networks | |
| 12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 | |
| Organisation | Algorithms and Complexity |
|
Briët, J., & Castro-Silva, D. (2023). Raising the roof on the threshold for Szemerédi‘s theorem with random differences. In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications, EUROCOMB'23 (pp. 231–237). doi:10.5817/CZ.MUNI.EUROCOMB23-032 |
|
