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

DOI10.37236/8929MaRDI QIDQ2290353zbMATH OpenOpenAlexFDO

Authors M. I. Isaev, Tejas Iyer, Brendan D. McKay

Publication date 27 January 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1908.01309, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p26

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Bradley-Terry model of paired comparisonssubdigraph occurrences in random orientations

Mathematics Subject Classification ID

Vertex degrees (05C07) Enumeration in graph theory (05C30)

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 $n^{1/3+varepsilon}$ for some $varepsilon>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.

Review text

Summary: 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+\varepsilon}\) for some \(\varepsilon > 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.

Recommendations

• Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
• Asymptotic enumeration of digraphs and bipartite graphs by degree sequence
• Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
• Asymptotic enumeration of graphs with given degree sequence
• Asymptotic enumeration by degree sequence of graphs of high degree

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Asymptotic behavior of the number of Eulerian orientations of graphs
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
• Asymptotic enumeration of tournaments with a given score sequence
• Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
• Complex martingales and asymptotic enumeration
• Degree sequences of random digraphs and bipartite graphs
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• scientific article; zbMATH DE number 3073477 (Why is no real title available?)
• Isoperimetric numbers of graphs
• Majorization, entropy and paired comparisons
• Maximal Flow Through a Network
• MM algorithms for generalized Bradley-Terry models.
• On the number of Eulerian orientations of a graph
• Random dense bipartite graphs and directed graphs with specified degrees
• Random regular tournaments
• Solution of a Ranking Problem from Binary Comparisons
• The asymptotic numbers of regular tournaments, Eulerian digraphs and Eulerian oriented graphs
• The Ranking of Incomplete Tournaments: A Mathematician's Guide to Popular Sports

Cited in

(6)

• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic behavior of the number of Eulerian orientations of graphs
• Asymptotic enumeration of Eulerian orientations for graphs with strong mixing properties
• Cumulant expansion for counting Eulerian orientations
• Random walks on Coxeter interchange graphs
• The football model, stochastic ordering and martingale transport

This page was built for publication: Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2290353)