Journal of Combinatorics
Volume 12 (2021)
Threshold functions for substructures in random subsets of finite vector spaces
Pages: 157 – 183
The study of substructures in random objects has a long history, beginning with Erdős and Rényi’s work on subgraphs of random graphs. We study the existence of certain substructures in random subsets of vector spaces over finite fields. First we provide a general framework which can be applied to establish coarse threshold results and prove a limiting Poisson distribution at the threshold scale. To illustrate our framework we apply our results to $k$-term arithmetic progressions, sums, right triangles, parallelograms and affine planes. We also find coarse thresholds for the property that a random subset of a finite vector space is sum-free, or is a Sidon set.
finite vector space, threshold property, Poisson distribution
2010 Mathematics Subject Classification
Changhao Chen was supported by Australian Research Council Discovery Project DP170100786.
Catherine Greenhill was supported by Australian Research Council Discovery Project DP140101519.
Received 10 May 2018
Accepted 29 May 2020
Published 4 January 2021