Directed Ramsey number for trees

Matija Bucić; Shoham Letzter; Benny Sudakov

doi:10.1016/j.endm.2017.06.035

Directed Ramsey number for trees

Matija Bucić, Shoham Letzter, Benny Sudakov

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

Abstract

Given an oriented graph H, the k-colour oriented Ramsey number of H, denoted by r→(H,k), is the least integer n, for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We show that r→(T,k)≤c_k|T|^k for any oriented tree T, which, in general, is tight up to a constant factor. We also obtain a stronger bound, when H is an arbitrarily oriented path.

Original language	English (US)
Pages (from-to)	169-175
Number of pages	7
Journal	Electronic Notes in Discrete Mathematics
Volume	61
DOIs	https://doi.org/10.1016/j.endm.2017.06.035
State	Published - Aug 2017
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Ramsey theory
directed graph
directed tree
tournament

Access to Document

10.1016/j.endm.2017.06.035

Cite this

@article{108c8109158f46fbaa48e3442f266487,

title = "Directed Ramsey number for trees",

abstract = "Given an oriented graph H, the k-colour oriented Ramsey number of H, denoted by r→(H,k), is the least integer n, for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We show that r→(T,k)≤ck|T|k for any oriented tree T, which, in general, is tight up to a constant factor. We also obtain a stronger bound, when H is an arbitrarily oriented path.",

keywords = "Ramsey theory, directed graph, directed tree, tournament",

author = "Matija Buci{\'c} and Shoham Letzter and Benny Sudakov",

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

year = "2017",

month = aug,

doi = "10.1016/j.endm.2017.06.035",

language = "English (US)",

volume = "61",

pages = "169--175",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Directed Ramsey number for trees

AU - Bucić, Matija

AU - Letzter, Shoham

AU - Sudakov, Benny

PY - 2017/8

Y1 - 2017/8

N2 - Given an oriented graph H, the k-colour oriented Ramsey number of H, denoted by r→(H,k), is the least integer n, for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We show that r→(T,k)≤ck|T|k for any oriented tree T, which, in general, is tight up to a constant factor. We also obtain a stronger bound, when H is an arbitrarily oriented path.

AB - Given an oriented graph H, the k-colour oriented Ramsey number of H, denoted by r→(H,k), is the least integer n, for which every k-edge-coloured tournament on n vertices contains a monochromatic copy of H. We show that r→(T,k)≤ck|T|k for any oriented tree T, which, in general, is tight up to a constant factor. We also obtain a stronger bound, when H is an arbitrarily oriented path.

KW - Ramsey theory

KW - directed graph

KW - directed tree

KW - tournament

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

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

U2 - 10.1016/j.endm.2017.06.035

DO - 10.1016/j.endm.2017.06.035

M3 - Article

AN - SCOPUS:85026786916

SN - 1571-0653

VL - 61

SP - 169

EP - 175

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Directed Ramsey number for trees

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this