Arcs in ${\mathbb{F}}_q^2$

An arc is a subset of ${\mathbb{F}}_q^2$ which does not contain any collinear triples. Let $A(q,k)$ denote the number of arcs in ${\mathbb{F}}_q^2$ with cardinality $k$. This paper is primarily concerned with estimating the size of $A(q,k)$ when $k$ is relatively large, namely $k=q^t$ for some $t>0$. Trivial estimates tell us that $$\left(\genfrac{}{}{0px}{}{q}{k}\right)\le A(q,k)\le \left(\genfrac{}{}{0px}{}{q^2}{k}\right)\mathrm{.}$$ We show that the behaviour of $A(q,k)$ changes significantly close to $t=1\mathrm{/}2$. Below this threshold an elementary argument is used to prove that the trivial upper bound above cannot be improved significantly. On the other hand, for $t\ge 1\mathrm{/}2+\delta$, we use the theory of hypergraph containers to get an improved upper bound $$A(q,k)\le \left(\genfrac{}{}{0px}{}{q^{2-t+2\delta }}{k}\right)\mathrm{.}$$ This technique is also used to give an upper bound for the size of the largest arc in a random subset of ${\mathbb{F}}_q^2$ which holds with high probability. For example, we prove that a $p$-random subset $Q \subset \mathbb F_q^2$with$q^{-3/2}<p<q^{-1}$containsanarcofsize$\Omega(q^{1/2})$ with high probability. The result is optimal for this range of $p$. Finally, this optimal bound for arcs in random sets is used to prove a finite field analogue of a result of Balogh and Solymosi, with a better exponent: there exists a subset $P\subset {\mathbb{F}}_q^2$ which does not contain any collinear quadruples, but with the property that for every $P^{\mathrm{\prime }}\subset P$ with $\mathrm{\mid }{P}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }P{\mathrm{\mid }}^{3\mathrm{/}4+o(1)}$, $P^{\mathrm{\prime }}$ contains a collinear triple.