Random Turán and counting results for general position sets over finite fields
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929720544722944 |
|---|---|
| author | Chen, Yaobin Liu, Xizhi Nie, Jiaxi Zeng, Ji |
| author_facet | Chen, Yaobin Liu, Xizhi Nie, Jiaxi Zeng, Ji |
| contents | Let $α(\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 $α(\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 $α(\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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_07744 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Random Turán and counting results for general position sets over finite fields Chen, Yaobin Liu, Xizhi Nie, Jiaxi Zeng, Ji Combinatorics Let $α(\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 $α(\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 $α(\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$. |
| title | Random Turán and counting results for general position sets over finite fields |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.07744 |