Counting restricted orientations of random graphs

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

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

zbMATH Keywords

random graphsforbidden digraphsrestricted orientations

Mathematics Subject Classification ID

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

Cites Work

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

Related Items (3)

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

Recommendations

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

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)