In the affine space \(\mathbb{F}_q^n\) over the finite field of order \(q\), a point set \(S\) is said to be \((d,k,r)\)-evasive if the intersection between \(S\) and any variety, of dimension \(k\) and degree at most \(d\), has cardinality less than \(r\). As \(q\) tends to infinity, the size of a \((d,k,r)\)-evasive set in \(\mathbb{F}_q^n\) is at most \(O(q^{n-k})\) by a simple averaging argument. We exhibit the existence of such evasive sets of sizes at least \(\Omega(q^{n-k})\) for much smaller values of \(r\) than previously known constructions, and establish an enumerative upper bound \(2^{O(q^{n-k})}\) for the total number of such evasive sets. The existence result is based on our study of twisted varieties. In the projective space \(\mathbb{P}^n\) over an algebraically closed field, a variety \(V\) is said to be \(d\)-twisted if the intersection between \(V\) and any variety of dimension \(n-\dim(V)\) and degree at most \(d\) has dimension zero. We prove an upper bound on the smallest possible degree of twisted varieties which is best possible in a mild sense. The enumeration result includes a new technique for the container method which we believe is of independent interest. To illustrate the potential of this technique, we give a simpler proof of a result by Chen–Liu–Nie–Zeng that characterizes the maximum size of a collinear-triple-free subset in a random sampling of \(\mathbb{F}_q^2\) up to polylogarithmic factors.

For an ordered point set in a Euclidean space or, more generally, in an abstract metric space, the ordered Nearest Neighbor Graph is obtained by connecting each of the points to its closest predecessor by a directed edge. We show that for every set of n points in R d , there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree at least log ⁡ n / ( 4 d ) . Apart from the 1 / ( 4 d ) factor, this bound is the best possible. As for the abstract setting, we show that for every n -element metric space, there exists an order such that the corresponding ordered Nearest Neighbor Graph has maximum degree Ω ( log ⁡ n / log ⁡ log ⁡ n ) .

In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons. That is, the set contains no $n$ points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.

Abstract. As a variant of the celebrated Szemerédi–Trotter theorem, Guth and Katz proved that [Formula: see text] points and [Formula: see text] lines in [Formula: see text] with at most [Formula: see text] lines in a common plane must determine at most [Formula: see text] incidences for [Formula: see text]. This upper bound is asymptotically tight and has an important application in the Erdős distinct distances problem. We characterize the extremal constructions towards the Guth–Katz bound by proving that such a large dense point-line arrangement must contain a [Formula: see text]-clique in general position provided [Formula: see text]. This is an analogue of a result by Solymosi for extremal Szemerédi–Trotter constructions in the plane.

A finite point set in $\mathbb{R}^d$ is in general position if no $d + 1$ points lie on a common hyperplane. Let $α_d(N)$ be the largest integer such that any set of $N$ points in $\mathbb{R}^d$, with no $d + 2$ members on a common hyperplane, contains a subset of size $α_d(N)$ in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that $α_2(N) < N^{5/6 + o(1)}$. In this paper, we also use the container method to obtain new upper bounds for $α_d(N)$ when $d \geq 3$. More precisely, we show that if $d$ is odd, then $α_d(N) < N^{\frac{1}{2} + \frac{1}{2d} + o(1)}$, and if $d$ is even, we have $α_d(N) < N^{\frac{1}{2} + \frac{1}{d-1} + o(1)}$. We also study the classical problem of determining $a(d,k,n)$, the maximum number of points selected from the grid $[n]^d$ such that no $k + 2$ members lie on a $k$-flat, and improve the previously best known bound for $a(d,k,n)$, due to Lefmann in 2008, by a polynomial factor when $k$ = 2 or 3 (mod 4).

A famous theorem of Erdős and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least √n. Here, we prove a positive fraction version of this theorem. For n > (k-1)², any sequence A of n distinct real numbers contains a collection of subsets A_1,…, A_k ⊂ A, appearing sequentially, all of size s = Ω(n/k²), such that every subsequence (a_1,…, a_k), with a_i ∈ A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1,…, A_k) described above is called block-monotone of depth k and block-size s. Our theorem is asymptotically best possible and follows from a more general Ramsey-type result for monotone paths, which we find of independent interest. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k²log k) block-monotone subsequences of depth at least k, upon deleting at most (k-1)² entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.