Directed graphs with lower orientation Ramsey thresholds

¹ Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090 São Paulo, Brazil
² Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK
³ Centre de Reserca Matemàtica, Edifici C, Campus Bellaterra, 08193 Bellaterra, Spain

^* Corresponding author: tnaia@member.fsf.org

Received: 13 November 2022
Accepted: 23 April 2024

Abstract

We investigate the threshold p_⃗H = p_⃗H (n) for the Ramsey-type property G(n, p) → ⃗H, where G(n, p) is the binomial random graph and G → ⃗H indicates that every orientation of the graph G contains the oriented graph ⃗ H as a subdigraph. Similarly to the classical Ramsey setting, the upper bound p_⃗H ⩽ Cn^{−1/m₂(⃗ H)} is known to hold for some constant C = C( ⃗ H), where m₂(⃗H) denotes the maximum 2-density of the underlying graph H of ⃗ H. While this upper bound is indeed the threshold for some ⃗H, this is not always the case. We obtain examples arising from rooted products of orientations of sparse graphs (such as forests, cycles and, more generally, subcubic {K₃, K_3,3}-free graphs) and arbitrarily rooted transitive triangles.