For fixed d ≥ 3, we construct subsets of the d-dimensional lattice cube [n]^d of size n^{3/(d + 1) - o(1)} with no d+2 points on a sphere or a hyperplane. This improves the previously best known bound of Ω(n^{1/(d-1)}) due to Thiele from 1995.

We prove that if a graph can be drawn in the plane such that each edge crosses at most k other edges, then it can be redrawn so that each edge participates in at most k³+O(k²) crossings. This improves the previous exponential bound that follows from a result of Schaefer and Štefankovič and answers a question of Ackerman and Schaefer.

We prove a far-reaching strengthening of Szemerédi's regularity lemma for intersection graphs of pseudo-segments. It shows that the vertex set of such a graph can be partitioned into a bounded number of parts of roughly the same size such that almost all bipartite graphs between different pairs of parts are complete or empty. We use this to get an improved bound on disjoint edges in simple topological graphs, showing that every $n$-vertex simple topological graph with no $k$ pairwise disjoint edges has at most $n(\log n)^{O(\log k)}$ edges.

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.

Given a complete simple topological graph G, a k-face generated by G is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle in G. Interestingly, there are complete simple topological graphs with the property that every odd face it generates contains the origin. In this paper, we show that every complete n-vertex simple topological graph generates at least Ω(n^{1/3}) pairwise disjoint 4-faces. As an immediate corollary, every complete simple topological graph on n vertices drawn in the unit square generates a 4-face with area at most O(n^{-1/3}). Finally, we investigate a ℤ₂ variant of Heilbronn’s triangle problem for not necessarily simple complete topological graphs.

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.

An r-quasiplanar graph is a graph drawn in the plane with no r pairwise crossing edges. Let s≥3 be an integer and r=2s. We prove that there is a constant C such that every r-quasiplanar graph with n≥r vertices has at most nCs−1logn2s−4 edges. A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every ϵ>0, there exists δ>0 such that every string graph with n vertices whose chromatic number is at least nϵ contains a clique of size at least nδ. A clique of this size or a coloring using fewer than nϵ colors can be found by a polynomial time algorithm in terms of the size of the geometric representation of the set of strings. In the process, we use, generalize, and strengthen previous results of Lee, Tomon, and others. All of our theorems are related to geometric variants of the following classical graph-theoretic problem of Erdős, Gallai, and Rogers. Given a Kr-free graph on n vertices and an integer s

Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

The famous Szemerédi–Trotter theorem states that any arrangement of n points and n lines in the plane determines $$O(n^{4/3})$$ incidences, and this bound is tight. In this paper, we prove the following Turán-type result for point-line incidence. Let $$\mathcal {L}_a$$ and $$\mathcal {L}_b$$ be two sets of t lines in the plane and let $$P=\{\ell _a \cap \ell _b : \ell _a \in \mathcal {L}_a, \,\ell _b \in \mathcal {L}_b\}$$ be the set of intersection points between $$\mathcal {L}_a$$ and $$\mathcal {L}_b$$ . We say that $$(P, \mathcal {L}_a \cup \mathcal {L}_b)$$ forms a natural $$t\times t$$ grid if $$|P| =t^2$$ , and $${\text {conv}}P$$ does not contain the intersection point of some two lines in $$\mathcal {L}_a$$ and does not contain the intersection point of some two lines in $$\mathcal {L}_b$$ . For fixed $$t > 1$$ , we show that any arrangement of n points and n lines in the plane that does not contain a natural $$t\times t$$ grid determines $$O(n^{{4}/{3}- \varepsilon })$$ incidences, where $$\varepsilon = \varepsilon (t)>0$$ . We also provide a construction of n points and n lines in the plane that does not contain a natural $$2 \times 2$$ grid and determines at least $$\Omega ({n^{1+{1}/{14}}})$$ incidences.

We consider m-colorings of the edges of a complete graph, where each color class is defined semi-algebraically with bounded complexity. The case m = 2 was first studied by Alon et al., who applied this framework to obtain surprisingly strong Ramsey-type results for intersection graphs of geometric objects and for other graphs arising in computational geometry. Considering larger values of m is relevant, e.g., to problems concerning the number of distinct distances determined by a point set. For p >= 3 and m >= 2, the classical Ramsey number R(p;m) is the smallest positive integer n such that any m-coloring of the edges of K_n, the complete graph on n vertices, contains a monochromatic K_p. It is a longstanding open problem that goes back to Schur (1916) to decide whether R(p;m)=2^{O(m)}, for a fixed p. We prove that this is true if each color class is defined semi-algebraically with bounded complexity, and that the order of magnitude of this bound is tight. Our proof is based on the Cutting Lemma of Chazelle et al., and on a Szemerédi-type regularity lemma for multicolored semi-algebraic graphs, which is of independent interest. The same technique is used to address the semi-algebraic variant of a more general Ramsey-type problem of Erdős and Shelah.

The Vapnik–Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every n-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $$e^{(\log n)^{1 - o(1)}}$$ . The dependence on the VC-dimension is hidden in the o(1) term. This improves the general lower bound, $$e^{c\sqrt{\log n}}$$ , due to Erdős and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result is almost optimal and nearly matches the celebrated Erdős–Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $$e^{\Omega (\log n)}$$ . Our results partially explain why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties. Our main tool is a partitioning result found by Lovász–Szegedy and Alon–Fischer–Newman, which is called the “ultra-strong regularity lemma” for graphs with bounded VC-dimension. We extend this lemma to k-uniform hypergraphs, and prove that the number of parts in the partition can be taken to be $$(1/\varepsilon )^{O(d)}$$ , improving the original bound of $$(1/\varepsilon )^{O(d^2)}$$ in the graph setting. We show that this bound is tight up to an absolute constant factor in the exponent. Moreover, we give an $$O(n^k)$$ -time algorithm for finding a partition meeting the requirements. Finally, we establish tight bounds on Ramsey–Turán numbers for graphs with bounded VC-dimension.

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in $k$, on the best constant $\delta>0$ such that the vertex classes $P_1,\ldots,P_k$ of every $k$-partite $k$-uniform semialgebraic hypergraph $H=(P_1\cup\cdots\cup P_k, E)$ with $|E|\ge\varepsilon\Pi_{j=1}^k|P_i|$ have, for $1 \leq i \leq k$, $\delta|P_i|$-element subsets $P'_i\subseteq P_i$ satisfying $P_{1}'\times\cdots\times P_{k}'\subseteq E$. The best previously known lower bound on $\delta$ due to Bukh and Hubard decreased triple exponentially fast in $k$. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets $P_1,\ldots,P_k\subset \mathbb{R}^d\; (k>d)$ have, for $1 \leq i \leq k$, subsets $P'_i$ of size at least $2^{-O(d^3k\log k)}|P_i|$ with the property that every $k$-tuple formed by taking one point from each $P'_i$ has the same order type. We also improve a result of Fox, Gromov, Lafforgue, Naor, and Pach, who established a regularity lemma for semialgebraic $k$-uniform hypergraphs of bounded complexity, showing that for each $\varepsilon>0$ the vertex set can be equitably partitioned into a bounded number of parts (in terms of $\varepsilon$ and the complexity) so that all but an $\varepsilon$-fraction of the $k$-tuples of parts are homogeneous. Here, we prove that the number of parts can be taken to be polynomial in $1/\varepsilon$. Our improved regularity lemma can be applied to geometric problems and to the following general question on property testing: is it possible to decide, with query complexity polynomial in the reciprocal of the approximation parameter, whether a hypergraph has a given hereditary property? We give an affirmative answer for testing typical hereditary properties for semialgebraic hypergraphs of bounded complexity.

A k-uniform semi-algebraic hypergraph H is a pair (P, E), where P is a subset of ℝd and E is a collection of k-tuples {p1, …, pk} ⊂ P such that (p1, …, pk) ∊ E if and only if the kd coordinates of the pi-s satisfy a boolean combination of a finite number of polynomial inequalities. The complexity of H can be measured by the number and the degrees of these inequalities and the number of variables (coordinates) kd. Several classical results in extremal hypergraph theory can be substantially improved when restricted to semi-algebraic hypergraphs. Substantially improving a theorem of Fox, Gromov, Lafforgue, Naor, and Pach, we establish the following “polynomial regularity lemma”: For any 0 < ε < 1/2, the vertex set of every k-uniform semi-algebraic hypergraph H = (P, E) can be partitioned into at most (1/ε)c parts P1, P2, …, as equal as possible, such that all but at most an ε-fraction of the k-tuples of parts (Pi1, …, Pik) are homogeneous in the sense that either every k-tuple (pi1, …, pik) ∊ Pi1 × … × Pik belongs to E or none of them do. Here c > 0 is a constant that depends on the complexity of H. We also establish an improved lower bound, single exponentially decreasing in k, on the best constant δ > 0 such that the vertex classes P1, …, Pk of every k-partite k-uniform semi-algebraic hypergraph H = (P1 ∪ … ∪ Pk, E) with |E| ≥ εΠkj=1|Pi| have, for 1 ≤ i ≤ k, δ|Pi|-element subsets P′i ⊆ Pi satisfying P′1 × … × P′k ⊆ E. The best previously known lower bound on δ due to Bukh and Hubard decreased double exponentially fast in k. We give three geometric applications of our results. In particular, we establish the following strengthening of the so-called same-type lemma of Bárány and Valtr: Any disjoint finite sets P1, …, Pk ⊂ ℝd (k > d) have for 1 ≤ i ≤ k subsets P′i of size at least 2−O(d3k log k)|Pi| with the property that every k-tuple formed by taking one point from each P′i has the same order type. The above techniques carry over to property testing. We show that for any typical hereditary hypergraph property , there is a randomized algorithm with query complexity ) to determine (with probability at least .99) whether a k-uniform semi-algebraic hypergraph H = (P,E) with constant description complexity is ε-near to having property , that is, whether one can change at most ε|P|k hyperedges of H in order to obtain a hypergraph that has the property. The testability of such properties for general k-uniform hypergraphs was first shown by Alon and Shapira (for graphs) and by Rödl and Schacht (for k > 2). The query complexity time of their algorithms is enormous, growing considerably faster than a tower function.

For natural numbers d and t there exists a positive C such that if F is a family of nC semi-algebraic sets in Rd of description complexity at most t, then there is a subset F' of F of size $n$ such that either every pair of elements in F' intersect or the elements of F' are pairwise disjoint. This result, which also holds if the intersection relation is replaced by any semi-algebraic relation of bounded description complexity, was proved by Alon, Pach, Pinchasi, Radoicic, and Sharir and improves on a bound of 4n for the family F which follows from a straightforward application of Ramsey's theorem. We extend this semi-algebraic version of Ramsey's theorem to k-ary relations and give matching upper and lower bounds for the corresponding Ramsey function, showing that it grows as a tower of height k-1. This improves on a direct application of Ramsey's theorem by one exponential. We apply this result to obtain new estimates for some geometric Ramsey-type problems relating to order types and one-sided sets of hyperplanes. We also study the off-diagonal case, achieving some partial results.

A graph drawn in the plane is called $k$-quasi-planar if it does not contain $k$ pairwise crossing edges. It has been conjectured for a long time that for every fixed $k$, the maximum number of edges of a $k$-quasi-planar graph with $n$ vertices is $O(n)$. The best known upper bound is $n(\log n)^{O(\log k)}$. In the present paper, we improve this bound to $(n\log n )2^{\alpha(n)^{c_k}}$ in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here $\alpha(n)$ denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for $k$-quasi-planar graphs in which every edge is drawn as an $x$-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most $2^{ck^6}n\log n$.

A curve $\gamma$ in the plane is $t$-monotone if its interior has at most $t-1$ vertical tangent points. A family of $t$-monotone curves $F$ is simple if any two members intersect at most once. It is shown that if $F$ is a simple family of $n$ $t$-monotone curves with at least $\epsilon n^2$ intersecting pairs (disjoint pairs), then there exists two subfamilies $F_1,F_2\subset F$ of size $\delta n$ each, such that every curve in $F_1$ intersects (is disjoint to) every curve in $F_2$, where $\delta$ depends only on $\epsilon$. We apply these results to find pairwise disjoint edges in simple topological graphs with $t$-monotone edges.

It is shown that every complete $n$-vertex simple topological graph has at least Ω(n1/3) pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Toth, which appears as problem 5 from chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.

Let C be a family of n convex bodies in the plane, which can be decomposed into k subfamilies of pairwise disjoint sets. It is shown that the number of tangencies between the members of C is at most O(kn), and that this bound cannot be improved. If we only assume that our sets are connected and vertically convex, that is, their intersection with any vertical line is either a segment or the empty set, then the number of tangencies can be superlinear in n, but it cannot exceed n(n log2 n). Our results imply a new upper bound on the number of regular intersection points on the boundary of *C.

A topological graph is a graph drawn in the plane with vertices represented by points and edges as arcs connecting its vertices. A k-grid in a topological graph is a pair of subsets of the edge set, each of size k, such that every edge in one subset crosses every edge in the other subset. It is known that for a fixed constant k, every n-vertex topological graph with no k-grid has O(n) edges.