2022/09/07 by Krishnendu Bhowmick, Bhowmick, Krishnendu, Oliver Roche‐Newton +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2209.03064
openalex publication_date 2022/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An arc in \mathbb Fq2 is a set P ⊂ \mathbb Fq2 such that no three points of P are collinear. We use the method of hypergraph containers to prove several counting results for arcs. Let \mathcal A(q) denote the family of all arcs in \mathbb Fq2. Our main result is the bound |\mathcal A(q)| ≤ 2(1+o(1))q. This matches, up to the factor hidden in the o(1) notation, the trivial lower bound that comes from considering all subsets of an arc of size q. We also give upper bounds for the number of arcs of a fixed (large) size. Let k=qt for some t >2/3, and let \mathcal A(q,k) denote the family of all arcs in \mathbb Fq2 with cardinality k. We prove that, for all γ>0 |\mathcal A(q,k)| ≤ \binom(1+γ)qk. This result improves a bound of Roche-Newton and Warren. A nearly matching lower bound |\mathcal A(q,k)| ≥ \binomqk follows by considering all subsets of size k of an arc of size q.