On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10436871" target="_blank" >RIV/00216208:11320/21:10436871 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-83823-2_23" target="_blank" >https://doi.org/10.1007/978-3-030-83823-2_23</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_23" target="_blank" >10.1007/978-3-030-83823-2_23</a>

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 geq 2$, an emph{ordered $k$-uniform hypergraph} $mathcal{H}=(H,&lt;)$ is a $k$-uniform hypergraph $H$ together with a fixed linear ordering $&lt;$ of its vertex set. The emph{ordered Ramsey number} $overline{R}(mathcal{H},mathcal{G})$ of two ordered $k$-uniform hypergraphs $mathcal{H}$ and $mathcal{G}$ is the smallest $N in mathbb{N}$ such that every red-blue coloring of the hyperedges of the ordered complete $k$-uniform hypergraph $mathcal{K}^{(k)}_N$ on $N$ vertices contains a blue copy of $mathcal{H}$ or a red copy of $mathcal{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 in mathbb{N}$ and for every ordered $3$-uniform hypergraph $mathcal{H}$ on $n$ vertices with maximum degree $d$ and with interval chromatic number $3$ there is an $varepsilon=varepsilon(d)&gt;0$ such that $$overline{R}(mathcal{H},mathcal{H}) leq 2^{O(n^{2-varepsilon})}.$$ In fact, we prove this upper bound for the number $overline{R}(mathcal{G},mathcal{K}^{(3)}_3(n))$, where $mathcal{G}$ is an ordered 3-uniform hypergraph with $n$ vertices and maximum degree $d$ and $mathcal{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 $overline{R}(mathcal{H},mathcal{K}^{(3)}_3(n)) geq 2^{Omega(nlog{n})}$ for some fixed ordered $3$-uniform hypergraph $mathcal{H}$.

Název v anglickém jazyce

On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs

Popis výsledku anglicky

For an integer $k geq 2$, an emph{ordered $k$-uniform hypergraph} $mathcal{H}=(H,&lt;)$ is a $k$-uniform hypergraph $H$ together with a fixed linear ordering $&lt;$ of its vertex set. The emph{ordered Ramsey number} $overline{R}(mathcal{H},mathcal{G})$ of two ordered $k$-uniform hypergraphs $mathcal{H}$ and $mathcal{G}$ is the smallest $N in mathbb{N}$ such that every red-blue coloring of the hyperedges of the ordered complete $k$-uniform hypergraph $mathcal{K}^{(k)}_N$ on $N$ vertices contains a blue copy of $mathcal{H}$ or a red copy of $mathcal{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 in mathbb{N}$ and for every ordered $3$-uniform hypergraph $mathcal{H}$ on $n$ vertices with maximum degree $d$ and with interval chromatic number $3$ there is an $varepsilon=varepsilon(d)&gt;0$ such that $$overline{R}(mathcal{H},mathcal{H}) leq 2^{O(n^{2-varepsilon})}.$$ In fact, we prove this upper bound for the number $overline{R}(mathcal{G},mathcal{K}^{(3)}_3(n))$, where $mathcal{G}$ is an ordered 3-uniform hypergraph with $n$ vertices and maximum degree $d$ and $mathcal{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 $overline{R}(mathcal{H},mathcal{K}^{(3)}_3(n)) geq 2^{Omega(nlog{n})}$ for some fixed ordered $3$-uniform hypergraph $mathcal{H}$.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

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)

Rok uplatnění

2021

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ů

Název statě ve sborníku

Extended Abstracts EuroComb 2021

ISBN

978-3-030-83823-2

ISSN

2297-0215

e-ISSN

2297-024X

Počet stran výsledku

6

Strana od-do

142-147

Název nakladatele

Springer International Publishing

Místo vydání

neuveden

Místo konání akce

Barcelona

Datum konání akce

6. 9. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—