Asymptotic enumeration of dense 0-1 matrices with specified line sums

Details Asymptotic enumeration of dense 0-1 matrices with specified line sums Asymptotic enumeration of dense 0-1 matrices with specified line sums

2006-06-20

arxiv.org/abs/math/0606496v2

Mathematics

Combinatorics

Multiple minor adjustments. Accepted by JCT-A

Scientific paper

Let S=(s_1,s_2,..., s_m) and T = (t_1,t_2,..., t_n) be vectors of non-negative integers with sum_{i=1}^{m} s_i = sum_{j=1}^n t_j. Let B(S,T) be the number of m*n matrices over {0,1} with j-th row sum equal to s_j for 1 <= j <= m and k-th column sum equal to t_k for 1 <= k <= n. Equivalently, B(S,T) is the number of bipartite graphs with m vertices in one part with degrees given by S, and n vertices in the other part with degrees given by T. Most research on the asymptotics of B(S,T) has focused on the sparse case, where the best result is that of Greenhill, McKay and Wang (2006). In the case of dense matrices, the only precise result is for the case of equal row sums and equal column sums (Canfield and McKay, 2005). This paper extends the analytic methods used by the latter paper to the case where the row and column sums can vary within certain limits. Interestingly, the result can be expressed by the same formula which holds in the sparse case.

Affiliated with

Also associated with

No associations

Rating

Asymptotic enumeration of dense 0-1 matrices with specified line sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic enumeration of dense 0-1 matrices with specified line sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic enumeration of dense 0-1 matrices with specified line sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-40329