اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAsymptotic enumeration of orientations of a graph as a function of the out-degree sequence
122
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
Let G be a simple connected graph of order n with degree sequence d_1, d_2, ..., d_n in non-increasing order. The spectral radius rho(G) of G is the largest eigenvalue of its adjacency matrix. For each positive integer L at most n, we give a sharp up
per bound for rho(G) by a function of d_1, d_2, ..., d_L, which generalizes a series of previous results.
The deck of a graph $G$ is the multiset of cards ${G-v:vin V(G)}$. Myrvold (1992) showed that the degree sequence of a graph on $ngeq7$ vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with av
erage degree $d$ can reconstructed from any deck missing $O(n/d^3)$ cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.
We study the distributional properties of horizontal visibility graphs associated with random restrictive growth sequences and random set partitions of size $n.$ Our main results are formulas expressing the expected degree of graph nodes in terms of
simple explicit functions of a finite collection of Stirling and Bernoulli numbers.
We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer $n$, what is the probability that a graph chosen uniformly at random from the set of graphs with $n$ vertices yields a
universally solvable game of Lights Out? When $n leq 11$, we compute this probability exactly by determining if the game is universally solvable for each graph with $n$ vertices. We approximate this probability for each positive integer $n$ with $n leq 87$ by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs.
We provide bivariate asymptotics for the poly-Bernoulli numbers, a combinatorial array that enumerates lonesum matrices, using the methods of Analytic Combinatorics in Several Variables (ACSV). For the diagonal asymptotic (i.e., for the special case
of square lonesum matrices) we present an alternative proof based on Parsevals identity. In addition, we provide an application in Algebraic Statistics on the asymptotic ML-degree of the bivariate multinomial missing data problem, and we strengthen an existing result on asymptotic enumeration of permutations having a specified excedance set.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
