Counting orientations of random graphs with no directed k‐cycles

For every k⩾3$$ k\geqslant 3 $$, 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$$ k $$. This solves a conjecture of Kohayakawa, Morris and the last two authors.

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2024-05, Vol.64 (3), p.676-691
Main Authors: Campos, Marcelo, Collares, Maurício, Mota, Guilherme Oliveira
Format: Article
Language:English
Subjects:
directed cycles
orientations
random graphs
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For every k⩾3$$ k\geqslant 3 $$, 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$$ k $$. This solves a conjecture of Kohayakawa, Morris and the last two authors.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.21196