Geodesic
Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
Mikhail Isaev ; Tejas Iyer1 ; Brendan D McKay2
1University of Birmingham
2Australian National University
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 $n^{1/3 + \epsilon}$ for some $\epsilon > 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.
DOI : 10.37236/8929
Classification : 05C30, 05C07
Mots-clés : Bradley-Terry model of paired comparisons, subdigraph occurrences in random orientations

Mikhail Isaev    ; Tejas Iyer  1   ; Brendan D McKay  2

1 University of Birmingham
2 Australian National University 
@article{10_37236_8929,
     author = {Mikhail Isaev and Tejas Iyer and Brendan D McKay},
     title = {Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8929},
     zbl = {1471.05046},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8929/}
}
TY  - JOUR
AU  - Mikhail Isaev
AU  - Tejas Iyer
AU  - Brendan D McKay
TI  - Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8929/
DO  - 10.37236/8929
ID  - 10_37236_8929
ER  - 
%0 Journal Article
%A Mikhail Isaev
%A Tejas Iyer
%A Brendan D McKay
%T Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8929/
%R 10.37236/8929
%F 10_37236_8929
Mikhail Isaev; Tejas Iyer; Brendan D McKay. Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8929

Cité par Sources :