Problem 1. Determine the asymptotic magnitude of \alpha4,2 (n), and more generally, of \alphad,k (n) for all fixed d and k.
Statement
Problem 1. Determine the asymptotic magnitude of \alpha4,2 (n), and more generally, of \alphad,k (n) for all fixed d and k. As another variation of the no-three-in-line problem, we consider the quan- tity \alpha(F2q , p), defined as the maximum size of a collinear-triple-free subset S in a p-random set of F2q , that is, the plane over the finite field of order q. Here, a p-random set is a random subset where each point is sampled uniformly indepen- dently with probability p. The second result of this talk characterizes \alpha(F2q , p) up to polylogarithmic factors for all possible values of p. Theorem 2 (Chen–Liu–Nie–Zeng [4]). As the prime power q \to \infty, asymptotically almost surely, we have Θ(pq 2 ), q −2+o(1) \leq p \leq q −3/2−o(1) , \alpha(F2q , p) = q 1/2+o(1) , q −3/2−o(1) \leq p \leq q −1/2+o(1) , Θ(pq), q −1/2+o(1) \leq p \leq 1. Moreover, all q o(1) factors here are polylogarithmic. This theorem is partially established by Roche-Newton–Warren [12] and Bhow- mick–Roche-Newton [2] previously for p within some smaller ranges. Following their approach, our proof is based on the container method. Specifically, we proved that there always exists a collection C of subsets (called containers) of F2q such that: (i) every collinear-triple-free subset of F2q is contained in some C \in C; (ii) |C| \leq 9q for all C \in C; and (iii) |C| \leq exp O(q 1/2 (log q)2 ) . We remark that container theorems of this type can also be applied to counting problems of collinear-triple- free subsets and their variants, see [12, 2, 4] for details. One of the key tools in our proof is the well-known hypergraph container lemma, proved independently by Balogh–Morris–Samotij [1] and Saxton–Thomason [14]. 188 Oberwolfach Report 3/2024 d showed that \alphad,k (n) \leq O n ⌊(k+2)/2⌋ , which behaves differently from Θ(nd−k ) for infinitely many values of d and k. The first result of this talk is an improvement of Lefmann’s upper bound. Theorem 1 (Suk–Zeng [15]). For fixed d and k, as n \to \infty, we have d 1 \alphad,k (n) \leq O n 2⌊(k+2)/4⌋ (1− 2⌊(k+2)/4⌋d+1 ) .
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.