Ramsey numbers of ordered graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10404409" target="_blank" >RIV/00216208:11320/20:10404409 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Rw5aFQuyQI" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Rw5aFQuyQI</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37236/7816" target="_blank" >10.37236/7816</a>
Alternative languages
Result language
angličtina
Original language name
Ramsey numbers of ordered graphs
Original language description
An ordered graph is a pair G=(G,<) where G is a graph and < is a total ordering of its vertices. The ordered Ramsey number R(G) is the minimum number N such that every ordered complete graph with N vertices and with edges colored by two colors contains a monochromatic copy of G. We show that there are arbitrarily large ordered matchings M_n on n vertices for which R(M_n) is superpolynomial in n. This implies that ordered Ramsey numbers of the same graph can grow superpolynomially in the size of the graph in one ordering and remain linear in another ordering. We also prove that the ordered Ramsey number R(G) is polynomial in the number of vertices of G if the bandwidth of G is constant or if G is an ordered graph of constant degeneracy and constant interval chromatic number.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1077-8926
e-ISSN
—
Volume of the periodical
2020
Issue of the periodical within the volume
27
Country of publishing house
US - UNITED STATES
Number of pages
32
Pages from-to
P1.16
UT code for WoS article
000506406700016
EID of the result in the Scopus database
2-s2.0-85078845229