Proof-Number Search is a best-first search algorithm with many successful applications, especially in game solving. As large-scale computing clusters become increasingly accessible, parallelization is a natural way to accelerate computation. However, existing parallel versions of Proof-Number Search are known to scale poorly on many CPU cores. Using two parallelized levels and shared information among workers, we present the first massively parallel version of Proof-Number Search that scales efficiently even on a large number of CPUs. We apply our solver, enhanced with Grundy numbers for reducing game trees of impartial games, to the Sprouts game, a case study motivated by the long-standing Sprouts Conjecture. Our algorithm achieves 332.9x speedup on 1024 cores, significantly improving previous parallelizations and outperforming the state-of-the-art Sprouts solver GLOP by four orders of magnitude in runtime while generating proofs 1,000x more complex. Despite exponential growth in game tree size, our solver verified the Sprouts Conjecture for 42 new positions, nearly doubling the number of known outcomes.

For a finite set P of points in the plane in general position, a crossing family of size k in P is a collection of k line segments with endpoints in P that are pairwise crossing. It is a long-standing open problem to determine the largest size of a crossing family in any set of n points in the plane in general position. It is widely believed that this size should be linear in n. Motivated by results from the theory of partitioning complete geometric graphs, we study a variant of this problem for point sets P that do not contain a non-crossing family of size m, which is a collection of 4 disjoint subsets P₁, P₂, P₃, and P₄ of P, each containing m points of P, such that for every choice of 4 points p_i ∈ P_i, the set {p₁,p₂,p₃,p₄} is such that p₄ is in the interior of the triangle formed by p₁,p₂,p₃. We prove that, for every m ∈ ℕ, each set P of n points in the plane in general position contains either a crossing family of size n/2^{O(√{log{m}})} or a non-crossing family of size m, by this strengthening a recent breakthrough result by Pach, Rubin, and Tardos (2021). Our proof is constructive and we show that these families can be obtained in expected time O(nm^{1+o(1)}). We also prove that a crossing family of size Ω(n/m) or a non-crossing family of size m in P can be found in expected time O(n).

Abstract. The celebrated Szemerédi–Trotter theorem states that the maximum number of incidences between [Formula: see text] points and [Formula: see text] lines in the plane is [Formula: see text], which is asymptotically tight. Solymosi (2005) conjectured that for any set of points [Formula: see text] and for any set of lines [Formula: see text] in the plane, the maximum number of incidences between [Formula: see text] points and [Formula: see text] lines in the plane whose incidence graph does not contain the incidence graph of [Formula: see text] is [Formula: see text]. This conjecture is mentioned in the book of Brass, et al. (2005) . Even a stronger conjecture, which states that the bound can be improved to [Formula: see text] for some [Formula: see text], was introduced by Mirzaei and Suk (2021) . We disprove both of these conjectures. We also introduce a new approach for proving the upper bound [Formula: see text] on the number of incidences for configurations [Formula: see text] that avoid certain subconfigurations.

Visualizing a graph $G$ in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently asked for each edge of $G$ to be drawn without crossings while allowing multiple different drawings of $G$. More formally, a collection $\mathcal{D}$ of drawings of $G$ is uncrossed if, for each edge $e$ of $G$, there is a drawing in $\mathcal{D}$ such that $e$ is uncrossed. The uncrossed number $\mathrm{unc}(G)$ of $G$ is then the minimum number of drawings in some uncrossed collection of $G$. No exact values of the uncrossed numbers have been determined yet, not even for simple graph classes. In this paper, we provide the exact values for uncrossed numbers of complete and complete bipartite graphs, partly confirming and partly refuting a conjecture posed by Hliněný and Masařík. We also present a strong general lower bound on $\mathrm{unc}(G)$ in terms of the number of vertices and edges of $G$. Moreover, we prove NP-hardness of the related problem of determining the edge crossing number of a graph $G$, which is the smallest number of edges of $G$ taken over all drawings of $G$ that participate in a crossing. This problem was posed as open by Schaefer in his book [Crossing Numbers of Graphs 2018].

Abstract. An obstacle representation of a graph [Formula: see text] consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of [Formula: see text] to points such that two vertices are adjacent in [Formula: see text] if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each [Formula: see text]-vertex graph is [Formula: see text] [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom., 59 (2018), pp. 143–164] and that there are [Formula: see text]-vertex graphs whose obstacle number is [Formula: see text] [V. Dujmović and P. Morin, Electron. J. Combin., 22 (2015), 3.1]. We improve this lower bound to [Formula: see text] for simple polygons and to [Formula: see text] for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of [Formula: see text]-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some [Formula: see text]-vertex graph is given as part of the input, then for some drawings [Formula: see text] obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph [Formula: see text] is fixed-parameter tractable in the vertex cover number of [Formula: see text]. Second, we show that, given a graph [Formula: see text] and a simple polygon [Formula: see text], it is NP-hard to decide whether [Formula: see text] admits an obstacle representation using [Formula: see text] as the only obstacle.

Given a set $S \subseteq \mathbb{R}^2$, define the \emph{Helly number of $S$}, denoted by $H(S)$, as the smallest positive integer $N$, if it exists, for which the following statement is true: for any finite family $\mathcal{F}$ of convex sets in~$\mathbb{R}^2$ such that the intersection of any $N$ or fewer members of~$\mathcal{F}$ contains at least one point of $S$, there is a point of $S$ common to all members of $\mathcal{F}$. We prove that the Helly numbers of \emph{exponential lattices} $\{α^n \colon n \in \mathbb{N}_0\}^2$ are finite for every $α>1$ and we determine their exact values in some instances. In particular, we obtain $H(\{2^n \colon n \in \mathbb{N}_0\}^2)=5$, solving a problem posed by Dillon (2021). For real numbers $α, β> 1$, we also fully characterize exponential lattices $L(α,β) = \{α^n \colon n \in \mathbb{N}_0\} \times \{β^n \colon n \in \mathbb{N}_0\}$ with finite Helly numbers by showing that $H(L(α,β))$ is finite if and only if $\log_α(β)$ is rational.

We consider point sets in the real projective plane ℝ𝒫² and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős-Szekeres-type problems. We provide asymptotically tight bounds for a variant of the Erdős-Szekeres theorem about point sets in convex position in ℝ𝒫², which was initiated by Harborth and Möller in 1994. The notion of convex position in ℝ𝒫² agrees with the definition of convex sets introduced by Steinitz in 1913. For k ≥ 3, an (affine) k-hole in a finite set S ⊆ ℝ² is a set of k points from S in convex position with no point of S in the interior of their convex hull. After introducing a new notion of k-holes for points sets from ℝ𝒫², called projective k-holes, we find arbitrarily large finite sets of points from ℝ𝒫² with no projective 8-holes, providing an analogue of a classical result by Horton from 1983. We also prove that they contain only quadratically many projective k-holes for k ≤ 7. On the other hand, we show that the number of k-holes can be substantially larger in ℝ𝒫² than in ℝ² by constructing, for every k ∈ {3,… ,6}, sets of n points from ℝ² ⊂ ℝ𝒫² with Ω(n^{3-3/5k}) projective k-holes and only O(n²) affine k-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in ℝ𝒫² and about some algorithmic aspects. The study of extremal problems about point sets in ℝ𝒫² opens a new area of research, which we support by posing several open problems.

For an integer $k \geq 2$, an ordered $k$-uniform hypergraph $\mathcal{H}=(H,<)$ is a $k$-uniform hypergraph $H$ together with a fixed linear ordering $<$ of its vertex set. The ordered Ramsey number $\overline{R}(\mathcal{H},\mathcal{G})$ of two ordered $k$-uniform hypergraphs $\mathcal{H}$ and $\mathcal{G}$ is the smallest $N \in \mathbb{N}$ such that every red-blue coloring of the hyperedges of the ordered complete $k$-uniform hypergraph $\mathcal{K}^{(k)}_N$ on $N$ vertices contains a blue copy of $\mathcal{H}$ or a red copy of $\mathcal{G}$. The ordered Ramsey numbers are quite extensively studied for ordered graphs, but little is known about ordered hypergraphs of higher uniformity. We provide some of the first nontrivial estimates on ordered Ramsey numbers of ordered 3-uniform hypergraphs. In particular, we prove that for all $d,n \in \mathbb{N}$ and for every ordered 3-uniform hypergraph $\mathcal{H}$ on $n$ vertices with maximum degree $d$ and with interval chromatic number 3 there is an $\varepsilon=\varepsilon(d)>0$ such that $\overline{R}(\mathcal{H},\mathcal{H}) \leq 2^{O(n^{2-\varepsilon})}.$ In fact, we prove this upper bound for the number $\overline{R}(\mathcal{G},\mathcal{K}^{(3)}_3(n))$, where $\mathcal{G}$ is an ordered 3-uniform hypergraph with $n$ vertices and maximum degree $d$, and $\mathcal{K}^{(3)}_3(n)$ is the ordered complete tripartite hypergraph with consecutive color classes of size $n$. We show that this bound is not far from the truth by proving $\overline{R}(\mathcal{H},\mathcal{K}^{(3)}_3(n)) \geq 2^{\Omega(n\log{n})}$ for some fixed ordered 3-uniform hypergraph $\mathcal{H}$.

Let d and k be integers with $$1 \le k \le d-1$$ . Let $$\Lambda $$ be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in $$\Lambda \cap K$$ . In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional $$n \times \cdots \times n$$ grid is at least $$\Omega \bigl (n^{d(d-k)/(d-1)-\varepsilon }\bigr )$$ and at most $$O\bigl (n^{d(d-k)/(d-1)}\bigr )$$ , where $$\varepsilon >0$$ is an arbitrarily small constant. This nearly settles a problem mentioned in the book by Brass et al. (Research problems in discrete geometry, Springer, New York, 2005). We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover $$\Lambda \cap K$$ . We use these new results to improve the best known lower bound for the maximum number of point–hyperplane incidences by Brass and Knauer (Comput Geom 25(1–2):13–20, 2003). For $$d \ge 3$$ and $$\varepsilon \in (0,1)$$ , we show that there is an integer $$r=r(d,\varepsilon )$$ such that for all positive integers n, m the following statement is true. There is a set of n points in $$\mathbb {R}^d$$ and an arrangement of m hyperplanes in $$\mathbb {R}^d$$ with no $$K_{r,r}$$ in their incidence graph and with at least $$\Omega \bigl ((mn)^{1-(2d+3)/((d+2)(d+3)) - \varepsilon }\bigr )$$ incidences if d is odd and $$\Omega \bigl ((mn)^{1-(2d^2+d-2)/((d+2)(d^2+2d-2)) -\varepsilon }\bigr )$$ incidences if d is even.

Let S be a subset of $$\mathbb {R}^d$$ with finite positive Lebesgue measure. The Beer index of convexity $${\text {b}}(S)$$ of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio $${\text {c}}(S)$$ of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate the relationship between these two natural measures of convexity. We show that every set $$S\subseteq \mathbb {R}^2$$ with simply connected components satisfies $${\text {b}}(S)\leqslant \alpha {\text {c}}(S)$$ for an absolute constant $$\alpha $$ , provided $${\text {b}}(S)$$ is defined. This implies an affirmative answer to the conjecture of Cabello et al. that this estimate holds for simple polygons. We also consider higher-order generalizations of $${\text {b}}(S)$$ . For $$1\leqslant k\leqslant d$$ , the k-index of convexity $${\text {b}}_k(S)$$ of a set $$S\subseteq \mathbb {R}^d$$ is the probability that the convex hull of a $$(k+1)$$ -tuple of points chosen uniformly independently at random from S is contained in S. We show that for every $$d\geqslant 2$$ there is a constant $$\beta (d)>0$$ such that every set $$S\subseteq \mathbb {R}^d$$ satisfies $${\text {b}}_d(S)\leqslant \beta {\text {c}}(S)$$ , provided $${\text {b}}_d(S)$$ exists. We provide an almost matching lower bound by showing that there is a constant $$\gamma (d)>0$$ such that for every $$\varepsilon \in (0,1)$$ there is a set $$S\subseteq \mathbb {R}^d$$ of Lebesgue measure 1 satisfying $${\text {c}}(S)\leqslant \varepsilon $$ and $${\text {b}}_d(S)\geqslant \gamma \frac{\varepsilon }{\log _2{1/\varepsilon }}\geqslant \gamma \frac{{\text {c}}(S)}{\log _2{1/{\text {c}}(S)}}$$ .

Let S be a subset of R^d with finite positive Lebesgue measure. The Beer index of convexity b(S) of S is the probability that two points of S chosen uniformly independently at random see each other in S. The convexity ratio c(S) of S is the Lebesgue measure of the largest convex subset of S divided by the Lebesgue measure of S. We investigate a relationship between these two natural measures of convexity of S. We show that every subset S of the plane with simply connected components satisfies b(S) <= alpha c(S) for an absolute constant alpha, provided b(S) is defined. This implies an affirmative answer to the conjecture of Cabello et al. asserting that this estimate holds for simple polygons. We also consider higher-order generalizations of b(S). For 1 <= k <= d, the k-index of convexity b_k(S) of a subset S of R^d is the probability that the convex hull of a (k+1)-tuple of points chosen uniformly independently at random from S is contained in S. We show that for every d >= 2 there is a constant beta(d) > 0 such that every subset S of R^d satisfies b_d(S) <= beta c(S), provided b_d(S) exists. We provide an almost matching lower bound by showing that there is a constant gamma(d) > 0 such that for every epsilon from (0,1] there is a subset S of R^d of Lebesgue measure one satisfying c(S) <= epsilon and b_d(S) >= (gamma epsilon)/log_2(1/epsilon) >= (gamma c(S))/log_2(1/c(S)).