5th workshop of the Center for Foundations of Modern Computer Science

5. workshop Centra základů moderní informatiky

The fifth workshop of the Center for Foundations of Modern Computer Science took place on Tuesday and Wednesday August 4 and 5, 2020, in Prague as a part of MCW XXV.

Abstracts

Ida Kantor: Souvenirs from Manhattan

When investigating lines in general metric spaces, the plane with the Manhattan metric provides a convenient playground, not trivial, and yet not too complex. Several ideas first discovered in the context of Manhattan metric later proved very useful in investigating general metric spaces. We will survey these and suggest possible directions for future research along these lines.

Martin Balko: On ordered Ramsey numbers of tripartite 3-uniform hypergraphs

For an integer k >= 2, an ordered k-uniform hypergraph H is a k-uniform hypergraph together with a fixed linear ordering of its vertex set. The ordered Ramsey number R(H,G) of two ordered k-uniform hypergraphs H and G is the smallest positive integer N such that every red-blue coloring of the hyperedges of the ordered complete k-uniform hypergraph K^(k)_N on N vertices contains a blue copy of H or a red copy of 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 positive integers d,n and for every ordered 3-uniform hypergraph H on n vertices with maximum degree d and with interval chromatic number 3 there is an epsilon=epsilon(d)>0 such that R(H,H) <= 2^(O(n^(2-epsilon))). In fact, we prove this upper bound for the number R(G,K^(3)_3(n)), where G is an ordered 3-uniform hypergraph with n vertices and maximum degree d and 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 R(H,K^(3)_3(n)) >= 2^(Omega(n\log(n))) for some fixed ordered 3-uniform hypergraph H.

This is joint work with Máté Vizer.