Vortrag zu „ordered Ramsey numbers“

13. August 2020

Vortrag

Zeitraum
13.08.2020
15:00 Uhr

Ort
FernUniversität, Gebäude 3, Universitätsstr. 11, 58097 Hagen, Raum H006

Veranstalter/-in
Lehrgebiet Diskrete Mathematik und Optimierung (Prof. Dr. Winfried Hochstättler)

Referent/-in
Prof. Martin Balko, Ph.D.
Karls-Universität in Prag
Prof. Balko ist Gast im Lehrgebiet Diskrete Mathematik und Optimierung

Der Vortrag zum Thema „On ordered Ramsey numbers of tripartite 3-uniform hypergraphs“ wird um 15 Uhr im Gebäude 3, Hybridraum H 006, der FernUniversität in Hagen stattfinden und über Zoom gestreamt, sodass Interessierte auch online teilnehmen können. Die Teilnahme ist frei, alle Interessierten sind willkommen.


Abstract:

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.

Joint work with Máté Vizer.

Interessierte, die per Zoom teilnehmen wollen, können sich bei Dr. Manfed Scheucher melden: manfred.scheucher

Gerd Dapprich | 31.07.2020