Arcs in F_q^2

DOI10.1016/J.EJC.2022.103512zbMATH Open1487.05038arXiv2003.03656OpenAlexW4213077935MaRDI QIDQ2136192FDOQ2136192

Authors: Oliver Roche-Newton, Audie Warren 

Publication date: 10 May 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: An arc is a subset of $mathbb{F}_q^2$ which does not contain any collinear triples. Let $A(q,k)$ denote the number of arcs in $mathbb{F}_q^2$ with cardinality $k$. This paper is primarily concerned with estimating the size of $A(q,k)$ when $k$ is relatively large, namely $k=q^t$ for some $t>0$. Trivial estimates tell us that [ {q choose k} leq A(q,k) leq {q^2 choose k}. ] We show that the behaviour of $A(q,k)$ changes significantly close to $t=1/2$. Below this threshold an elementary argument is used to prove that the trivial upper bound above cannot be improved significantly. On the other hand, for $tgeq1/2+delta$, we use the theory of hypergraph containers to get an improved upper bound [ A(q,k) leq {q^{2-t+2delta} choose k}. ] This technique is also used to give an upper bound for the size of the largest arc in a random subset of $mathbb{F}_q^2$ which holds with high probability. For example, we prove that a $p$-random subset $Qsubsetmathbb{F}_q^2$ with $q^{-3/2}<p<q^{-1}$ contains an arc of size $Omega(q^{1/2})$ with high probability. The result is optimal for this range of $p$. Finally, this optimal bound for arcs in random sets is used to prove a finite field analogue of a result of Balogh and Solymosi, with a better exponent: there exists a subset $Psubsetmathbb{F}_q^2$ which does not contain any collinear quadruples, but with the property that for every $P^{\prime }subsetP$ with $|P^{\prime }|geq|P{|}^{3/4+o(1)}$, $P^{\prime }$ contains a collinear triple.

Full work available at URL: https://arxiv.org/abs/2003.03656

Recommendations

• Extending small arcs to large arcs
• Small complete arcs in projective planes
• scientific article; zbMATH DE number 1383301
• Arcs, blocking sets, and minihypers
• On sizes of complete arcs in \(PG(2,q)\)

zbMATH Keywords

\(p\)-random setCounting \(k\)-arcs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of finite geometries (05B25) Enumeration in graph theory (05C30) Hypergraphs (05C65) Combinatorial structures in finite projective spaces (51E20)

Cites Work

• Extremal results for random discrete structures
• Combinatorial theorems in sparse random sets
• Hypergraph containers
• Independent sets in hypergraphs
• Title not available (Why is that?)
• Ovals In a Finite Projective Plane
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• For which densities are random triangle-free graphs almost surely bipartite?
• A Lower Bound for Heilbronn'S Problem
• Formula for the number of [9,3] MDS codes
• Applications of graph containers in the Boolean lattice
• An Asymptotic Formula in <inline-formula> <tex-math notation="TeX">\(q\) </tex-math></inline-formula> for the Number of <inline-formula> <tex-math notation="TeX">\([n, k]~q\) </tex-math></inline-formula>-Ary MDS Codes
• On the number of points in general position in the plane
• Four‐term progression free sets with three‐term progressions in all large subsets

Cited In (7)

• Primitive arcs in \(\mathrm{PG}(2,q)\)
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Arcs in \(\mathbb Z^2_{2p}\)
• The values \(\sqrt {2q}\) and \(\log _{2}q\):\, their relationship with \(k\)-arcs.
• Counting arcs in \(\mathbb{F}_q^2\)
• Upper bounds for the number of substructures in finite geometries from the container method
• Cyclic arcs in \(\mathrm{PG}(2,q)\)

This page was built for publication: Arcs in \(\mathbb{F}_q^2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136192)