We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of n points that are the vertices of a convex n-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this n-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex k-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning k-gons: in the monochromatic version the points of both players can make up a k-gon, while in the bichromatic version only Maker’s points contribute to such a polygon. Both settings are studied in this paper. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place s points per round, for any constant $$s \ge 1$$ , Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place s points per round for any constant $$s<2$$ . This settles an open problem posed in 2019. Furthermore, we show that there are games that are not a lost cause for Breaker. Whenever $$k\ge 8$$ and Breaker is allowed to play 12 or more points per round, she has a winning strategy. We also consider the one-round bichromatic game (a.k.a. the offline version). In this setting, we show that Breaker wins if she can place twice as many points as Maker but if the bias is less than 2, then Maker wins for large enough set of points.

We prove a fractional Helly theorem for k-flats intersecting fat convex sets. A family ℱ of sets is said to be ρ-fat if every set in the family contains a ball and is contained in a ball such that the ratio of the radii of these balls is bounded by ρ. We prove that for every dimension d and positive reals ρ and α there exists a positive β = β(d,ρ, α) such that if ℱ is a finite family of ρ-fat convex sets in ℝ^d and an α-fraction of the (k+2)-size subfamilies from ℱ can be hit by a k-flat, then there is a k-flat that intersects at least a β-fraction of the sets of ℱ. We prove spherical and colorful variants of the above results and prove a (p,k+2)-theorem for k-flats intersecting balls.

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant ε ∈ (0,1), one could construct a (2 + ε )-spanner with O (n log(n )) edges (SICOMP 2019), and there is a lower bound of Ω(n2) edges for any (2 — ε )-spanner (SoCG 2015). The main open question is whether a linear number of edges suffices and the stretch can be reduced to 2. We resolve this problem by showing that for stretch 2, one needs Ω(n log n ) edges, and for stretch 2 + ε for any fixed ε ∈ (0,1), O (n ) edges are sufficient. Our lower bound is the first super-linear lower bound for stretch 2.

We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0’s and 1’s in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.

We study exak(n,F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k=0 is the Turán number ex(n,F) that is among the most studied parameters in extremal graph theory. We show that for any F and k, exak(n,F)=(1+o(1))ex(n,F) and determine the exact values of exak(n,K3) and exa1(n,Kr) for n large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order n that consists of an unknown copy of F and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least n2−exa1(n,F). Among other results we show that the number of queries that were answered NO is at least n2−exa1(n,F).

Abstract In a colouring of $${\mathbb {R}}^d$$ R d a pair $$(S,s_0)$$ ( S , s 0 ) with $$S\subseteq {\mathbb {R}}^d$$ S ⊆ R d and with $$s_0\in S$$ s 0 ∈ S is almost-monochromatic if $$S\setminus \{s_0\}$$ S \ { s 0 } is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs $$(S,s_0)$$ ( S , s 0 ) in colourings of $${\mathbb {R}}^d$$ R d , $${\mathbb {Z}}^d$$ Z d , and of $${\mathbb {Q}}$$ Q under some restrictions on the colouring. Among other results, we characterise those $$(S,s_0)$$ ( S , s 0 ) with $$S\subseteq {\mathbb {Z}}$$ S ⊆ Z for which every finite colouring of $${\mathbb {R}}$$ R without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of $$(S,s_0)$$ ( S , s 0 ) . We also show that if $$S\subseteq {\mathbb {Z}}^d$$ S ⊆ Z d and $$s_0$$ s 0 is outside of the convex hull of $$S\setminus \{s_0\}$$ S \ { s 0 } , then every finite colouring of $${\mathbb {R}}^d$$ R d without a monochromatic similar copy of $${\mathbb {Z}}^d$$ Z d contains an almost-monochromatic similar copy of $$(S,s_0)$$ ( S , s 0 ) . Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of $$\chi ({{\mathbb {R}}}^2)\ge 5$$

Abstract Define the k-th Radon number $$r_k$$ r k of a convexity space as the smallest number (if it exists) for which any set of $$r_k$$ r k points can be partitioned into k parts whose convex hulls intersect. Combining the recent abstract fractional Helly theorem of Holmsen and Lee with earlier methods of Bukh, we prove that $$r_k$$ r k grows linearly, i.e., $$r_k\le c(r_2)\cdot k$$ r k ≤ c ( r 2 ) · k .

In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\cal F$ covering an $n$-element ground set which satisfies the following condition: for any two disjoint members $A, B\in\cal F$, there exist $a\in A$ and $b\in B$ such that either $B\cup\{a\}\in\cal F$ and $A\cup\{b\}\setminus\{a\}\in\cal F$, or $A\cup\{b\}\in\cal F$ and $B\cup\{a\}\setminus\{b\}\in\cal F$. Denoting by $f(n)$ the smallest cardinality of such a family $\cal F$, they proved that $f(n)<2^{O(\sqrt{n}\log n)}$, and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito, Avvakumov, and Karasev is not far from optimal; we show that $2^{(1.42+o(1))\sqrt{n}}\le f(n)\le 2^{(1+o(1))\sqrt{2n\log n}}$. We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members $A, B\in\cal F$ with $|A|>|B|$, there exists $a\in A$ such that $B\cup\{a\}\in\cal F$. In this case, we prove that the size of the smallest $\cal F$ satisfying this stronger condition lies between $2^{\Omega(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$.

Dang et al. have given an algorithm that can find a Tarski fixed point in a k -dimensional lattice of width n using O (log k n ) queries [ 2 ]. Multiple authors have conjectured that this algorithm is optimal [ 2 , 7 ], and indeed this has been proven for two-dimensional instances [ 7 ]. We show that these conjectures are false in dimension three or higher by giving an O (log 2 n ) query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for k -dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an O (log 2 ⌈k/3⌉ n ) query algorithm for the k -dimensional problem.

We improve the upper bound for the maximum possible number of stable matchings among$n$jobs and$n$applicants from 131072n+ O(1) to 3.55n+ O(1). To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(Kn)=n−b(n), where b(n) is the number of 1’s in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n−b(n)≤m(G)≤n−1. We show that for any tree T on an even number of vertices we have m(T)=n−1, and that for any tree T on an odd number of vertices, we have n−65≤m(T)≤n−2. Our proof uses results about the weighted version of the problem for Kn, which may be of independent interest. We also exhibit a sequence Gn of graphs with m(Gn)=n−b(n) such that Gn has O(nb(n)) edges and n vertices.

In a colouring of ℝ^d a pair (S,s₀) with S ⊆ ℝ^d and with s₀ ∈ S is almost-monochromatic if S⧵{s₀} is monochromatic but S is not. We consider questions about finding almost-monochromatic similar copies of pairs (S,s₀) in colourings of ℝ^d, ℤ^d, and of ℚ under some restrictions on the colouring. Among other results, we characterise those (S,s₀) with S ⊆ ℤ for which every finite colouring of ℝ without an infinite monochromatic arithmetic progression contains an almost-monochromatic similar copy of (S,s₀). We also show that if S ⊆ ℤ^d and s₀ is outside of the convex hull of S⧵{s₀}, then every finite colouring of ℝ^d without a monochromatic similar copy of ℤ^d contains an almost-monochromatic similar copy of (S,s₀). Further, we propose an approach based on finding almost-monochromatic sets that might lead to a human-verifiable proof of χ(ℝ²) ≥ 5.

What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors? It is known that the answer to this question is either three or four. We show that three colors always suffice if the condition must be satisfied only by disks that contain a fixed point. Our result also holds, and is even tight, when instead of disks we consider their topological generalization, namely, pseudo-disks, with a nonempty intersection. Our solution uses the equivalence that a hypergraph can be realized by stabbed pseudo-disks if and only if it is ABAB-free. These hypergraphs are defined in a purely abstract, combinatorial way, and our proof that they are 3-chromatic is also combinatorial.

We study whether for a given planar family $${\mathcal {F}}$$ there is an m such that any finite set of points can be 3-colored so that any member of $${\mathcal {F}}$$ that contains at least m points contains two points with different colors. We conjecture that if $${\mathcal {F}}$$ is a family of pseudo-disks, then such an m exists. We prove this in the special case when $${\mathcal {F}}$$ is the family of all homothetic copies of a given convex polygon. We also study the problem in higher dimensions.

The Hanani–Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani–Tutte theorem in the case when each cluster induces a connected subgraph.Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum (UM) colorings and conflict-free (CF) colorings. In a UM coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a CF coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We consider the corresponding UM and CF chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.

We settle a problem of Dujmović, Eppstein, Suderman, and Wood by showing that there exists a function $f$ with the property that every planar graph $G$ with maximum degree $d$ admits a drawing with noncrossing straight-line edges, using at most $f(d)$ different slopes. If we allow the edges to be represented by polygonal paths with one bend, then $2d$ slopes suffice. Allowing two bends per edge, every planar graph with maximum degree $d\ge 3$ can be drawn using segments of at most $\lceil d/2\rceil$ different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. Every other planar graph requires exactly $\lceil d/2\rceil$ slopes.

A well-studied special case of bin packing is the 3-partition problem , where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O (log n ) additional bins. The three-permutations-problem of Beck is the following. Given any three permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy . We establish a surprising connection between bin packing and Beck’s problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of three permutations. This connection yields an alternative method to establish an O (log n ) bound on the additive integrality gap of the 3-partition. Conversely, making use of a recent example of three permutations, for which a discrepancy of Ω(log n ) is necessary, we prove the following: The O (log 2 n ) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.

Let ℱ be a family of pairs of sets. We call it an (a, b)-set system if for every set-pair (A,B) in ℱ we have that |A| = a, |B| = b, and A ∩ B = Ø. Furthermore, ℱ is weakly cross-intersecting if for any (Ai , Bi ), (Aj , Bj ) ∈ ℱ with i ≠ j we have th

A well studied special case of bin packing is the 3-partition problem, where n items of size > ¼ have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory. We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of [1].

We consider the problem of testing whether the maximum additive integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomial time if the number of constraints is fixed. It turns out that this generalization is NP-hard even if the number of constraints is fixed. However, if, in addition, the objective is the all-one vector, then one can test in polynomial time whether the additive gap is bounded by a constant.