Oriented Ramsey numbers of graded digraphs

2024/05/02 by Patryk Morawski, Yuval Wigderson, Morawski, Patryk +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2405.01069

openalex publication_date 2024/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that any graded digraph D on n vertices with maximum degree Δ has an oriented Ramsey number of at most C^Δn for some absolute constant C > 1, improving upon a recent result of Fox, He, and Wigderson. In particular, this implies that oriented grids in any fixed dimension have linear oriented Ramsey numbers, and gives a polynomial bound on the oriented Ramsey number of the hypercube. We also show that this result is essentially best possible, in that there exist graded digraphs on n vertices with maximum degree Δ such that their oriented Ramsey number is at least c^Δn for some absolute constant c > 1.

Related

• Ramsey numbers of digraphs with local edge structure
• The oriented size Ramsey number of directed paths
• Degrees in oriented hypergraphs and Ramsey p-chromatic number
• Oriented Ramsey numbers of some sparse graphs
• A note on some embedding problems for oriented graphs