ON ORDERED RAMSEY NUMBERS OF TRIPARTITE 3-UNIFORM HYPERGRAPHS

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10453258" target="_blank" >RIV/00216208:11320/22:10453258 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JxGzS2gVCU" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JxGzS2gVCU</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/21M1404958" target="_blank" >10.1137/21M1404958</a>

Result language

angličtina

Original language name

ON ORDERED RAMSEY NUMBERS OF TRIPARTITE 3-UNIFORM HYPERGRAPHS

Original language description

For an integer k &gt;= 2, an ordered k-uniform hypergraph H = (H, &lt;) is a k-uniform hypergraph H together with a fixed linear ordering &lt; of its vertex set. The ordered Ramsey number (R) over bar (H, G) of two ordered k-uniform hypergraphs H and G is the smallest N is an element of N such that every red-blue coloring of the hyperedges of the ordered complete k-uniform hypergraph K-N((k)) 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 d, n is an element of 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) &gt; 0 such that (R) over bar (H, H) &lt;= 2(O)(n(2)(-epsilon)). In fact, we prove this upper bound for the number (R) over bar (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) over bar (H, K-3((3))(n)) &gt;= 2(Omega(n log n)) for some fixed ordered 3-uniform hypergraph H.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GJ18-13685Y" target="_blank" >GJ18-13685Y: Model thoery and extremal combinatorics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

1095-7146

Volume of the periodical

36

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

214-228

UT code for WoS article

000778502000011

EID of the result in the Scopus database

2-s2.0-85130609169