Counting orientations of random graphs with no directed k‐cycles

DOI10.1002/RSA.21196arXiv2209.03339MaRDI QIDQ6201038

Guilherme Oliveira Mota, Maurício Collares, Marcelo Campos

Publication date: 25 March 2024

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

Abstract: For every $kgeq3$, we determine the order of growth, up to polylogarithmic factors, of the number of orientations of the binomial random graph containing no directed cycle of length $k$. This solves a conjecture of Kohayakawa, Morris and the last two authors.

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

zbMATH Keywords

random graphsorientationsdirected cycles

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• On the number of orientations of random graphs with no directed cycles of a given length
• On the number of graphs without 4-cycles
• Counting independent sets in graphs
• The number of oriantations having no fixed tournament
• Counting orientations of graphs with no strongly connected tournaments
• Counting H-free orientations of graphs
• Counting restricted orientations of random graphs
• The Theory of Round Robin Tournaments

This page was built for publication: Counting orientations of random graphs with no directed k‐cycles