Counting restricted orientations of random graphs

2018/11/07 by Collares, Maurício, Kohayakawa, Yoshiharu, Morris, Robert +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.03080

Abstract

We count orientations of G(n,p) avoiding certain classes of oriented graphs. In particular, we study T_r(n,p), the number of orientations of the binomial random graph G(n,p) in which every copy of K_r is transitive, and S_r(n,p), the number of orientations of G(n,p) containing no strongly connected copy of K_r. We give the correct order of growth of log T_r(n,p) and log S_r(n,p) up to polylogarithmic factors; for orientations with no cyclic triangle, this significantly improves a result of Allen, Kohayakawa, Mota and Parente. We also discuss the problem for a single forbidden oriented graph, and state a number of open problems and conjectures.

Related

• Counting graph orientations with no directed triangles
• Counting degree-constrained subgraphs and orientations
• Subgraphs of weakly quasi-random oriented graphs
• Counting orientations of graphs with no strongly connected tournaments
• Counting degree-constrained orientations