On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
Original language description
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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)