Ordered size Ramsey number of paths

József Balogh; Felix Christian Clemen; Emily Heath; Mikhail Lavrov

doi:10.1016/j.dam.2019.02.002

Ordered size Ramsey number of paths

József Balogh, Felix Christian Clemen, Emily Heath, Mikhail Lavrov

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path P_n to be the monotone increasing path with n edges. The ordered size Ramsey number r̃(P_r,P_s) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of P_r or a blue copy of P_s. For 2≤r≤s, we show [Formula presented], where C>0 is an absolute constant. This problem is motivated by the recent results of Bucić et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

Original language	English (US)
Pages (from-to)	13-18
Number of pages	6
Journal	Discrete Applied Mathematics
Volume	276
DOIs	https://doi.org/10.1016/j.dam.2019.02.002
State	Published - Apr 15 2020

Keywords

Ordered graphs
Paths
Ramsey numbers

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/j.dam.2019.02.002

Library availability

Discover UIUC Full Text

Cite this

@article{f35d764202b94f23b9b1ba4fb3c4b65c,

title = "Ordered size Ramsey number of paths",

abstract = "An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path Pn to be the monotone increasing path with n edges. The ordered size Ramsey number {\~r}(Pr,Ps) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of Pr or a blue copy of Ps. For 2≤r≤s, we show [Formula presented], where C>0 is an absolute constant. This problem is motivated by the recent results of Buci{\'c} et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.",

keywords = "Ordered graphs, Paths, Ramsey numbers",

author = "J{\'o}zsef Balogh and Clemen, {Felix Christian} and Emily Heath and Mikhail Lavrov",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier B.V.",

year = "2020",

month = apr,

day = "15",

doi = "10.1016/j.dam.2019.02.002",

language = "English (US)",

volume = "276",

pages = "13--18",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Ordered size Ramsey number of paths

AU - Balogh, József

AU - Clemen, Felix Christian

AU - Heath, Emily

AU - Lavrov, Mikhail

PY - 2020/4/15

Y1 - 2020/4/15

N2 - An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path Pn to be the monotone increasing path with n edges. The ordered size Ramsey number r̃(Pr,Ps) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of Pr or a blue copy of Ps. For 2≤r≤s, we show [Formula presented], where C>0 is an absolute constant. This problem is motivated by the recent results of Bucić et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

AB - An ordered graph is a simple graph with an ordering on its vertices. Define the ordered path Pn to be the monotone increasing path with n edges. The ordered size Ramsey number r̃(Pr,Ps) is the minimum number m for which there exists an ordered graph H with m edges such that every two-coloring of the edges of H contains a red copy of Pr or a blue copy of Ps. For 2≤r≤s, we show [Formula presented], where C>0 is an absolute constant. This problem is motivated by the recent results of Bucić et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

KW - Ordered graphs

KW - Paths

KW - Ramsey numbers

UR - http://www.scopus.com/inward/record.url?scp=85062419013&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062419013&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.02.002

DO - 10.1016/j.dam.2019.02.002

M3 - Article

AN - SCOPUS:85062419013

SN - 0166-218X

VL - 276

SP - 13

EP - 18

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Ordered size Ramsey number of paths

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this