Orientation Ramsey thresholds for cycles and cliques

DOI10.1137/20M1386463zbMATH Open1479.05348arXiv2012.08632OpenAlexW3214745248MaRDI QIDQ5013576FDOQ5013576

Authors: Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa, Tássio Naia 

Publication date: 1 December 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: If $G$ is a graph and $vecH$ is an oriented graph, we write $GovecH$ to say that every orientation of the edges of $G$ contains $vecH$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{vecH}=p_{vecH}(n)$ for the property $G(n,p)ovecH$ for the cases in which $vecH$ is an acyclic orientation of a complete graph or of a cycle.

Full work available at URL: https://arxiv.org/abs/2012.08632

Recommendations

• Ramsey properties of orientations of graphs
• Arbitrary orientations of Hamilton cycles in oriented graphs
• On the number of orientations of random graphs with no directed cycles of a given length
• scientific article; zbMATH DE number 881276
• Arbitrary orientations of Hamilton cycles in digraphs

zbMATH Keywords

thresholdorientationrandom graphsRamsey

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Digraphs
• The Voting Problem
• Title not available (Why is that?)
• Graph theory
• Threshold functions
• On the KŁR conjecture in random graphs
• A proof of Sumner's universal tournament conjecture for large tournaments
• Title not available (Why is that?)
• Trees in tournaments
• Paths and Cycles in Tournaments
• On an anti-Ramsey threshold for sparse graphs with one triangle
• Title not available (Why is that?)
• Ramsey properties of orientations of graphs
• An approximate version of Sumner's universal tournament conjecture
• Title not available (Why is that?)
• Trees in tournaments
• Trees in tournaments
• A short proof of the random Ramsey theorem
• On claws belonging to every tournament
• Claws contained in all \(n\)-tournaments
• Largest digraphs contained in all n-tournaments
• An algorithmic framework for obtaining lower bounds for random Ramsey problems
• On the unavoidability of oriented trees
• On avoidable and unavoidable claws
• Monochromatic trees in random tournaments
• Anti-Ramsey threshold of cycles
• Unavoidable trees in tournaments
• Title not available (Why is that?)

Cited In (8)

• Title not available (Why is that?)
• On the number of orientations of random graphs with no directed cycles of a given length
• On oriented relative clique number
• Word-representable graphs: orientations, posets, and bounds
• Directed graphs with lower orientation Ramsey thresholds
• Orientability Thresholds for Random Hypergraphs
• Ramsey properties of orientations of graphs
• The Multiple-Orientability Thresholds for Random Hypergraphs

This page was built for publication: Orientation Ramsey thresholds for cycles and cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013576)