Counting restricted orientations of random graphs

DOI10.1002/RSA.20904MaRDI QIDQ5128751zbMATH OpenOpenAlexWikidataFDO

Authors Maurício Collares, Yoshiharu Kohayakawa, Robert Morris, G. O. Mota

Publication date 26 October 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphsforbidden digraphsrestricted orientations

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30)

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.

Recommendations

• Degree constrained orientations in countable graphs
• Counting degree-constrained subgraphs and orientations
• On the number of orientations of random graphs with no directed cycles of a given length
• On the \(k\)-orientability of random graphs
• Counting H-free orientations of graphs
• Acyclic orientations of random graphs
• A note on orientations of the infinite random graph
• A new approach to the orientation of random hypergraphs
• Counting and sampling orientations on chordal graphs

Cites work

• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 3487496 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• Graph bootstrap percolation
• On the number of orientations of random graphs with no directed cycles of a given length
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• Searching for acyclic orientations of graphs
• The number of oriantations having no fixed tournament
• The probabilistic method
• Threshold Functions for Ramsey Properties
• Threshold functions for extension statements

Cited in

(8)

• Counting H-free orientations of graphs
• On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
• On the number of \(r\)-transitive orientations of \(G(n,p)\)
• Counting orientations of random graphs with no directed k‐cycles
• On the number of orientations of random graphs with no directed cycles of a given length
• A note on counting orientations
• Counting orientations of graphs with no strongly connected tournaments
• Subgraphs of weakly quasi-random oriented graphs

This page was built for publication: Counting restricted orientations of random graphs

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