Ordered size Ramsey number of paths

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

Research output: Contribution to journalArticlepeer-review

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ć et al. (2019) and Letzter and Sudakov (2019) for oriented graphs.

Original languageEnglish (US)
Pages (from-to)13-18
Number of pages6
JournalDiscrete Applied Mathematics
Volume276
DOIs
StatePublished - Apr 15 2020

Keywords

  • Ordered graphs
  • Paths
  • Ramsey numbers

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Ordered size Ramsey number of paths'. Together they form a unique fingerprint.

Cite this