Directed-cycle orientation-counting conjecture

Let CkC_k^\circlearrowright denote the directed cycle of length kk, and let D(G(n,p),Ck)D(G(n,p),C_k^\circlearrowright) be the number of orientations of G(n,p)G(n,p) containing no copy of CkC_k^\circlearrowright. Directed-cycle orientation-counting conjecture. If pn1+1/(k1)p\gg n^{-1+1/(k-1)}, then, with high probability,

logD(G(n,p),Ck)=Θ(np1/(k2)+nlogn).\log D(G(n,p),C_k^\circlearrowright)=\Theta\left(\frac{n}{p^{1/(k-2)}}+n\log n\right).

This conjecture proposes a sharp form of the paper's bounds for directed cycles: the first term matches the known lower-bound scale, while the conjectured expression also accounts for the nlognn\log n contribution. The source does not provide a resolution.

Sources & referencesView supporting material

Primary source

Marcelo Campos, Maurício Collares and Guilherme Oliveira Mota, “Counting orientations of random graphs with no directed k-cycles”, arXiv:2209.03339 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.