Strongly connected tournament orientation-counting conjecture

About 13 years old · traced to

Let H⃗\vec{H} be a strongly connected tournament with k:=v(H)⩾4k:=v(H)\geqslant 4, and let p≫n−2/(k+1)p\gg n^{-2/(k+1)}. Tournament orientation-counting conjecture. Then, with high probability,

log⁡D(G(n,p),H⃗)=Θ~(np(k−1)/2).\log D(G(n,p),\vec{H})=\widetilde{\Theta}\left(\frac{n}{p^{(k-1)/2}}\right).

Estimating the number of H⃗\vec{H}-free orientations remains open for strongly connected tournaments with at least four vertices; a more general version of this conjecture appeared in earlier work.

References

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).

Additional references

3 papers in this index state this conjecture (2013–2022). The statement above is taken from the most recent of them; the others are arXiv:1811.03080, arXiv:1307.4803.

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.