Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence

Mikhail Isaev, Tejas Iyer, Brendan D. McKay

Research output: Contribution to journalArticleResearchpeer-review

Abstract

We prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph G. The graph G is assumed to have average degrees at least n1/3+ε for some ε > 0, and to have strong mixing properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.

Original languageEnglish
Article numberP1.26
Number of pages30
JournalElectronic Journal of Combinatorics
Volume27
Issue number1
DOIs
Publication statusPublished - 1 Jan 2020

Cite this