Large line-free sets and their applications

In this paper, we construct explicit families of polynomials $P\in {\mathbb{F}}_q[x_1,\dots ,x_n]$ with large root sets which have restricted intersections with affine lines. We use these sets to make substantial progress on a number of problems in extremal combinatorics. For each prime power $q$ and integer $2\le t\le q-1$, we construct $t$-line evasive subsets of ${\mathbb{F}}_q^n$ of size $$q^{n(1-\frac{2}{t^2+t})},$$ which is significantly larger than those previously known. Moreover, our method yields a partition of ${\mathbb{F}}_q^n$ into such sets. We extend this partitioning result to the projective space $PG(n,q)$, obtaining the first explicit colorings for the vector space Ramsey number $R_q(2;k)$ that exhibit dependence on both $q$ and $k$. In particular, we show that $$R_q(2;k)>\frac{(q-1)k}{2}-O_q(1),$$ improving recent bounds. Finally, we apply these constructions to extremal graph theory and improve the best-known bounds on the bipartite Turán number $\mathrm{e}\mathrm{x}(n,m,\{C_4,{\theta }_{3,t}\})$. Most notably, we show that $$\mathrm{e}\mathrm{x}(n,n^{2\mathrm{/}3},\{C_4,{\theta }_{3,3}\})=\mathrm{\Theta }(n^{1+1\mathrm{/}9}),$$ making progress on a question originally posed by Erdős.