On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10436873" target="_blank" >RIV/00216208:11320/21:10436873 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-030-83823-2_38" target="_blank" >https://doi.org/10.1007/978-3-030-83823-2_38</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-83823-2_38" target="_blank" >10.1007/978-3-030-83823-2_38</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
Popis výsledku v původním jazyce
For two ordered graphs $G^<$ and $H^<$, the emph{ordered Ramsey number} $r_<(G^<,H^<)$ is the minimum $N$ such that every red-blue coloring of the edges of the ordered complete graph $K^<_N$ contains a red copy of~$G^<$ or a blue copy of $H^<$. For $n in mathbb{N}$, a emph{nested matching} $NM^<_n$ is the ordered graph on $2n$ vertices with edges ${i,2n-i+1}$ for every $i=1,dots,n$. We improve bounds on the numbers $r_<(NM^<_n,K^<_3)$ obtained by Rohatgi, we disprove his conjecture about these numbers, and we determine them exactly for $n=4,5$. This gives a stronger lower bound on the maximum chromatic number of $k$-queue graphs for every $k geq 3$. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are $n$-good for every $ninmathbb{N}$. In particular, we discover a new class of such ordered trees, extending all previously known examples.
Název v anglickém jazyce
On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
Popis výsledku anglicky
For two ordered graphs $G^<$ and $H^<$, the emph{ordered Ramsey number} $r_<(G^<,H^<)$ is the minimum $N$ such that every red-blue coloring of the edges of the ordered complete graph $K^<_N$ contains a red copy of~$G^<$ or a blue copy of $H^<$. For $n in mathbb{N}$, a emph{nested matching} $NM^<_n$ is the ordered graph on $2n$ vertices with edges ${i,2n-i+1}$ for every $i=1,dots,n$. We improve bounds on the numbers $r_<(NM^<_n,K^<_3)$ obtained by Rohatgi, we disprove his conjecture about these numbers, and we determine them exactly for $n=4,5$. This gives a stronger lower bound on the maximum chromatic number of $k$-queue graphs for every $k geq 3$. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are $n$-good for every $ninmathbb{N}$. In particular, we discover a new class of such ordered trees, extending all previously known examples.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
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ů
Údaje specifické pro druh výsledku
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
7
Strana od-do
241-247
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
—