Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-193 | 22nd November 2024 20:53

Reasonable Bounds for Combinatorial Lines of Length Three

RSS-Feed




TR24-193
Authors: Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
Publication: 22nd November 2024 20:58
Downloads: 623
Keywords: 


Abstract:

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 \Omega((\log^* n)^{-1/2}) of [D.H.J. Polymath, Ann. of Math. 2012].



ISSN 1433-8092 | Imprint