Arcs in F_q^2

DOI10.1016/J.EJC.2022.103512MaRDI QIDQ2136192zbMATH OpenOpenAlexFDO

Authors Oliver Roche-Newton, Audie Warren

Publication date 10 May 2022

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

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

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)

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.

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)\)

Cites work

• A Lower Bound for Heilbronn'S Problem
• 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
• Applications of graph containers in the Boolean lattice
• Combinatorial theorems in sparse random sets
• Extremal results for random discrete structures
• For which densities are random triangle-free graphs almost surely bipartite?
• Formula for the number of [9,3] MDS codes
• Four‐term progression free sets with three‐term progressions in all large subsets
• Hypergraph containers
• Independent sets in hypergraphs
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• On the number of points in general position in the plane
• Ovals In a Finite Projective Plane
• The maximum size of a Sidon set contained in a sparse random set of integers

Cited in

(7)

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

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)