Pith. sign in

Random Tur\'an and counting results for general position sets over finite fields

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

Let $\alpha(\mathbb{F}_q^d,p)$ denote the maximum size of a general position set in a $p$-random subset of $\mathbb{F}_q^d$. We determine the order of magnitude of $\alpha(\mathbb{F}_q^2,p)$ up to polylogarithmic factors for all possible values of $p$, improving the previous results obtained by Roche-Newton--Warren and Bhowmick--Roche-Newton. For $d \ge 3$ we prove upper bounds for $\alpha(\mathbb{F}_q^d,p)$ that are essentially tight within certain ranges for $p$. We establish the upper bound $2^{(1+o(1))q}$ for the number of general position sets in $\mathbb{F}_q^d$, which matches the trivial lower bound $2^{q}$ asymptotically in the exponent. We also refine this counting result by proving an asymptotically tight (in the exponent) upper bound for the number of general position sets with a fixed size. The latter result for $d=2$ improves a result of Roche-Newton--Warren. Our proofs are grounded in the hypergraph container method, and additionally, for $d=2$ we also leverage the pseudorandomness of the point-line incidence graph of $\mathbb{F}_{q}^2$.

citation-role summary

background 1

citation-polarity summary

fields

math.CO 1

years

2024 1

verdicts

CONDITIONAL 1

roles

background 1

polarities

unclear 1

representative citing papers

Subset Selection Problems in Planar Point Sets

math.CO · 2024-12-18 · conditional · novelty 6.0

The paper proves new asymptotic upper and lower bounds for three subset-selection problems on planar point sets with at most s collinear points.

citing papers explorer

Showing 1 of 1 citing paper.

  • Subset Selection Problems in Planar Point Sets math.CO · 2024-12-18 · conditional · none · ref 5 · internal anchor

    The paper proves new asymptotic upper and lower bounds for three subset-selection problems on planar point sets with at most s collinear points.