ON ORDERED RAMSEY NUMBERS OF TRIPARTITE 3-UNIFORM HYPERGRAPHS
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
ON ORDERED RAMSEY NUMBERS OF TRIPARTITE 3-UNIFORM HYPERGRAPHS
Popis výsledku v původním jazyce
For an integer k >= 2, an ordered k-uniform hypergraph H = (H, <) is a k-uniform hypergraph H together with a fixed linear ordering < 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) > 0 such that (R) over bar (H, H) <= 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)) >= 2(Omega(n log n)) for some fixed ordered 3-uniform hypergraph H.
Název v anglickém jazyce
ON ORDERED RAMSEY NUMBERS OF TRIPARTITE 3-UNIFORM HYPERGRAPHS
Popis výsledku anglicky
For an integer k >= 2, an ordered k-uniform hypergraph H = (H, <) is a k-uniform hypergraph H together with a fixed linear ordering < 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) > 0 such that (R) over bar (H, H) <= 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)) >= 2(Omega(n log n)) for some fixed ordered 3-uniform hypergraph H.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GJ18-13685Y" target="_blank" >GJ18-13685Y: Teorie modelů a extrémální kombinatorika</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
1095-7146
Svazek periodika
36
Číslo periodika v rámci svazku
1
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
15
Strana od-do
214-228
Kód UT WoS článku
000778502000011
EID výsledku v databázi Scopus
2-s2.0-85130609169