Výsledky projektu Kombinatorické struktury a diskrétní geometrie

We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in $\mathbb{R}^d$. A $k$-ary semialgebraic predicate $\Phi(x_1,\ldots,x_k)$ on $\mathbb{R}^d$ is a Boolean combination of polynomial equations and inequalities in the $kd$ coordinates of $k$ points $x_1,\ldots,x_k\in\mathbb{R}^d$. A sequence $P=(p_1,\ldots,p_n)$ of points in $\mathbb{R}^d$ is called $\Phi$-homogeneous if either $\Phi(p_{i_1}, \ldots,p_{i_k})$ holds for all choices $1\le i_1<\cdots<i_k\le n$, or it holds for no such choice. The Ramsey function $R_\Phi(n)$ is the smallest $N$ such that every point sequence of length $N$ contains a $\Phi$-homogeneous subsequence of length $n$. Conlon et al. constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every $k\ge 4$, they exhibit a $k$-ary $\Phi$ in dimension $2^{k-4}$ with $R_\Phi$ bounded below by a tower of height k-1. We reduce the dimension in their construction, obtaining a $k$-ary semialgebraic predicate $\Phi$ on $\mathbb{R}^{k-3}$ with $R_\Phi$ bounded below by a tower of height k-1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence $P$ in $\mathbb{R}^d$ order-type homogeneous if all (d+1)-tuples in $P$ have the same orientation. Every sufficiently long point sequence in general position in $\mathbb{R}^d$ contains an order-type homogeneous subsequence of length $n$, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Bárány, Matoušek, and Pór, our results imply a tower function of $\Omega(n)$ of height $d$ as a lower bound, matching an upper bound by Suk up to the constant in front of $n$.

In 1958, Hill conjectured that the minimum number of crossings in a drawing of $K_n$ is exactly $Z(n) = \frac{1}{4} \lfloor\frac{n}{2}\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor$. Generalizing the result by \'{A}brego {\it et al.} for 2-page book drawings, we prove this conjecture for plane drawings in which edges are represented by $x$-monotone curves. In fact, our proof shows that the conjecture remains true for $x$-monotone drawings of $K_n$ in which adjacent edges may cross an even number of times, and instead of the crossing number we count the pairs of edges which cross an odd number of times.

We further discuss a generalization of this result to shellable drawings, a notion introduced by \'{A}brego {\it et al.} We also give a combinatorial characterization of several classes of $x$-monotone drawings of complete graphs using a small set of forbidden configurations. For a similar local characterization of shellable drawings, we generalize Carath\'eodory's theorem to simple drawings of complete graphs.

Let $P=(p_1,p_2,\ldots,p_N)$ be a sequence of points in the plane, where $p_i=(x_i,y_i)$ and $x_1<x_2<\cdots<x_N$. A famous 1935 Erd\H{o}s–Szekeres theorem asserts that every such $P$ contains a monotone subsequence $S$ of $\lceil \sqrt{N} \rceil$ source points. Another, equally famous theorem from the same paper implies that every such $P$ contains a convex or concave subsequence of $\Omega(\log N)$ points.

Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a $(k+1)$-tuple $K\subseteq P$ to be positive if it lies on the graph of a function whose $k$th derivative is everywhere nonnegative, and similarly for a negative $(k+1)$-tuple. Then we say that $S\subseteq P$ is $k$th-order monotone if its $(k+1)$-tuples are all positive or all negative.

We investigate a quantitative bound for the corresponding Ramsey-type result (i.e., how large $k$th-order monotone subsequence can be guaranteed in every $N$-point $P$). We obtain an $\Omega(\log(k−1)N)$ lower bound ($(k−1)$-times iterated logarithm). This is based on a quantitative Ramsey-type theorem for transitive colorings of the complete $(k+1)$-uniform hypergraph (these were recently considered by Pach, Fox, Sudakov, and Suk).

For $k=3$, we construct a geometric example providing an $O(\log\log N)$ upper bound, tight up to a multiplicative constant. As a consequence, we obtain similar upper bounds for a Ramsey-type theorem for order-type homogeneous subsets in $\mathbb{R}^3$, as well as for a Ramsey-type theorem for hyperplanes in $\mathbb{R}^4$ recently used by Dujmovi\'{c} and Langerman.

A grid drawing of a graph maps vertices to the grid $\mathbb{Z}^{d}$ and edges to line segments that avoid grid points representing other vertices. We show that a graph $G$ is $q^{d}$-colorable, $d$, $q \geq 2$, if and only if there is a grid drawing of $G$ in $\mathbb{Z}^{d}$ in which no line segment intersects more than $q$ grid points. This strengthens the result of D.~Flores Pe\H{n}aloza and F.~J.~Zaragoza Martinez. Second, we study grid drawings with a bounded number of columns, introducing some new $\NP$-complete problems. Finally, we show that any planar graph has a planar grid drawing where every line segment contains exactly two grid points. This result proves conjectures asked by D.~Flores Pe\H{n}aloza and F.~J.~Zaragoza Martinez.