On ordered Ramsey numbers of matchings versus triangles

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10473473" target="_blank" >RIV/00216208:11320/23:10473473 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-013" target="_blank" >https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-013</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-013" target="_blank" >10.5817/CZ.MUNI.EUROCOMB23-013</a>

Result language

angličtina

Original language name

On ordered Ramsey numbers of matchings versus triangles

Original language description

For graphs $G^&lt;$ and $H^&lt;$ with linearly ordered vertex sets, the emph{ordered Ramsey number} $r_&lt;(G^&lt;,H^&lt;)$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete ordered graph $K^&lt;_N$ on $N$ vertices contains either a blue copy of $G^&lt;$ or a red copy of $H^&lt;$.Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_&lt;(M^&lt;,K^&lt;_3)$ where $M^&lt;$ is an ordered matching on $n$ vertices.We prove that almost all $n$-vertex ordered matchings $M^&lt;$ with interval chromatic number 2 satisfy $r_&lt;(M^&lt;,K^&lt;_3) in Omega((n/log n)^{5/4})$ and $r_&lt;(M^&lt;,K^&lt;_3) in O(n^{7/4})$, improving a recent result by Rohatgi (2019).We also show that there are $n$-vertex ordered matchings $M^&lt;$ with interval chromatic number at least 3 satisfying $r_&lt;(M^&lt;,K^&lt;_3) in Omega((n/log n)^{4/3})$, which asymptotically matches the best known lower bound on these off-diagonal ordered Ramsey numbers for general $n$-vertex ordered matchings.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>

Continuities

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

Publication year

2023

Confidentiality

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

Article name in the collection

Proceedings of the 12th European Conference onCombinatorics, Graph Theory and Applications

ISBN

978-80-280-0344-9

ISSN

2788-3116

e-ISSN

—

Number of pages

7

Pages from-to

94-100

Publisher name

Masaryk University Press

Place of publication

Praha

Event location

Praha

Event date

Aug 28, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—