Abstract

This thesis is devoted to Ramsey-type problems, most of which are motivated by problems from discrete geometry. We focus on Ramsey-type results for ordered structures such as ordered graphs and hypergraphs. In particular, we introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for hypergraphs with a linear ordering on their vertices, and we study the growth rate of ordered Ramsey numbers of ordered hypergraphs with respect to the numbers of their vertices. We prove several results about ordered Ramsey numbers, present applications in discrete geometry, and solve open problems and conjectures of several authors. The proofs of our results are based on various techniques, including computer-aided proofs.

First, we find ordered matchings whose ordered Ramsey numbers grow superpolynomially, which is in sharp contrast with the situation for unordered bounded-degree graphs, whose Ramsey numbers grow only linearly. We then show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth, which solves an open problem of Conlon, Fox, Lee, and Sudakov. Answering another question of Conlon, Fox, Lee, and Sudakov, we find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering.

We derive the exact formula for ordered Ramsey numbers of monotone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles, improving previous bounds by Károlyi et al. Using state-of-art SAT solvers, we refute a conjecture of Peters and Szekeres from 2006 about a strengthening of the famous Erdős-Szekeres conjecture to ordered hypergraphs.

Making a progress on the famous Hill's conjecture about the crossing numbers of complete graphs, we obtain the exact formula for the minimum number of crossings in x-monotone drawings of complete graphs. We also provide a combinatorial characterization of these drawings in terms of colorings of ordered complete 3-uniform hypergraphs. Finally, we derive the best known lower bound on the psedudolinear crossing number of complete graphs using an approach based on simulated annealing.


Selected publications

On ordered Ramsey numbers of bounded-degree graphs

(with V. Jelínek and P. Valtr), submitted, 2016.

Bounding the pseudolinear crossing number of K_n via simulated annealing

(with J. Kynčl), extended abstract in the Proceedings of the XVI Spanish Meeting on Computational Geometry, pages 37-40, 2015.

A SAT attack on the Erdos-Szekeres conjecture

(with P. Valtr), to appear in European Journal of Combinatorics.

Extended abstract in Electronic Notes in Discrete Mathematics 49, pages 425-431, 2015.

Ramsey numbers of ordered graphs

(with J. Cibulka, K. Král, and J. Kynčl), submitted, 2016.

Extended abstract in Electronic Notes in Discrete Mathematics 49, pages 419-424, 2015.

Crossing numbers and combinatorial characterization of monotone drawings of K_n

(with R. Fulek and J. Kynčl), Discrete and Computational Geometry 53(1), pages 107-143, 2015.

Extended abstract in the Proceedings of the XV Spanish Meeting on Computational Geometry, pages 127-130, 2013.

Contact Details

Martin Balko
Department of Applied Mathematics
Faculty of Mathematics and Physics, Charles University in Prague

Malostranské nám. 2/25, 118 00 Praha 1
balko@kam.mff.cuni.cz