Maximum in-general-position set in a random subset of ${\mathbb{F}}_q^d$

Abstract

Let $\hat{I}\pm ({\mathbb{F}}_q^d,p)$ be the maximum possible size of a point set in general position in a $p$-random subset of ${\mathbb{F}}_q^d$. We determine the order of magnitude of $\hat{I}\pm ({\mathbb{F}}_q^d,p)$ up to a polylogarithmic factor by proving the balanced supersaturation conjecture of Balogh and Luo. Our result also resolves a conjecture implicitly posed by the first author, Liu, the second author and Zeng. In the course of our proof, we establish a lemma that demonstrates a ``structure vs. randomness'' phenomenon for point sets in finite-field linear spaces, which may be of independent interest.

25 pages, 1 figures