Ramsey numbers of ordered graphs
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Ramsey numbers of ordered graphs
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Ramsey numbers of ordered graphs
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2020
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 periodika
Electronic Journal of Combinatorics
ISSN
1077-8926
e-ISSN
—
Svazek periodika
2020
Číslo periodika v rámci svazku
27
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
32
Strana od-do
P1.16
Kód UT WoS článku
000506406700016
EID výsledku v databázi Scopus
2-s2.0-85078845229