Counting restricted orientations of random graphs

DOI10.1002/RSA.20904zbMATH Open1451.05210arXiv1811.03080OpenAlexW3000224941WikidataQ122111935 ScholiaQ122111935MaRDI QIDQ5128751FDOQ5128751

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

Publication date: 26 October 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Threshold functions for extension statements
• The probabilistic method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold Functions for Ramsey Properties
• The number of oriantations having no fixed tournament
• On the number of orientations of random graphs with no directed cycles of a given length
• Title not available (Why is that?)
• Graph bootstrap percolation
• Optimal Randomized Algorithms for Local Sorting and Set-Maxima
• Searching for acyclic orientations of graphs

Cited In (3)

• Counting H-free orientations of graphs
• Counting orientations of random graphs with no directed k‐cycles
• Counting orientations of graphs with no strongly connected tournaments

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)