Journal of Combinatorics

Volume 12 (2021)

Number 1

Threshold functions for substructures in random subsets of finite vector spaces

Pages: 157 – 183

DOI: https://dx.doi.org/10.4310/JOC.2021.v12.n1.a6

Authors

Changhao Chen (Department of Mathematics, Chinese University of Hong Kong)

Catherine Greenhill (School of Mathematics and Statistics, University of New South Wales (UNSW), Sydney, Australia)

Abstract

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.

Keywords

finite vector space, threshold property, Poisson distribution

2010 Mathematics Subject Classification

05B25, 60C05

Full Text (PDF format)

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