Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums

Let s=(s₁,…,s_m) and t=(t₁,…,t_n) be vectors of non-negative integer-valued functions with equal sum . Let N(s,t) be the number of m×n matrices with entries from {0,1} such that the ith row has row sum s_i and the jth column has column sum t_j. Equivalently, N(s,t) is the number of labelled bipartite graphs with degrees of the vertices in one side of the bipartition given by s and the degrees of the vertices in the other side given by t. We give an asymptotic formula for N(s,t) which holds when S→∞ with 1?st=o(S^2/3), where and . This extends a result of McKay and Wang [Linear Algebra Appl. 373 (2003) 273-288] for the semiregular case (when s_i=s for 1?i?m and t_j=t for 1?j?n). The previously strongest result for the non-semiregular case required 1?max{s,t}=o(S^1/4), due to McKay [Enumeration and Design, Academic Press, Canada, 1984, pp. 225-238].     

Random dense bipartite graphs and directed graphs with specified degrees

Let s and t be vectors of positive integers with the same sum. We study the uniform distribution on the space of simple bipartite graphs with degree sequence s in one part and t in the other; equivalently, binary matrices with row sums s and column sums t . In particular, we find precise formulae for the probabilities that a given bipartite graph is edge‐disjoint from, a subgraph of, or an induced subgraph of a random graph in the class. We also give similar formulae for the uniform distribution on the set of simple directed graphs with out‐degrees s and in‐degrees t . In each case, the graphs or digraphs are required to be sufficiently dense, with the degrees varying within certain limits, and the subgraphs are required to be sufficiently sparse. Previous results were restricted to spaces of sparse graphs. Our theorems are based on an enumeration of bipartite graphs avoiding a given set of edges, proved by multidimensional complex integration. As a sample application, we determine the expected permanent of a random binary matrix with row sums s and column sums t . © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

We consider the set Σ(R,C) of all m×n matrices having 0-1 entries and prescribed row sums R=(r₁,…,rm) and column sums C=(c₁,…,cn). We prove an asymptotic estimate for the cardinality |Σ(R,C)| via the solution to a convex optimization problem. We show that if Σ(R,C) is sufficiently large, then a random matrix D∈Σ(R,C) sampled from the uniform probability measure in Σ(R,C) with high probability is close to a particular matrix Z=Z(R,C) that maximizes the sum of entropies of entries among all matrices with row sums R, column sums C and entries between 0 and 1. Similar results are obtained for 0-1 matrices with prescribed row and column sums and assigned zeros in some positions.     

Asymptotic enumeration of 2-covers and line graphs

A 2-cover is a multiset of subsets of [n]?{1,2,…,n} such that each element of [n] lies in exactly two of the subsets. A 2-cover is called proper if all of the subsets are distinct, and is called restricted if any two of them intersect in at most one element.In this paper we find asymptotic enumerations for the number of line graphs on n labelled vertices and for 2-covers.We find that the number s_n of 2-covers and the number t_n of proper 2-covers both have asymptotic growth

     

Asymptotic enumeration of RNA secondary structure

Based on the new representation of RNA secondary structures, we obtain the basic relations about secondary structures with a prescribed size m for hairpin loops and minimum stack length l. Furthermore, we make an asymptotic analysis on RNA secondary structures with certain additional constrains.     

On the number of disjoint pairs of S-permutation matrices

In [R. Fontana, Fraction of permutations, an application to Sudoku, Journal of Statistical Planning and Inference 141 (2011) 3697–3704], Roberto Fontana offers an algorithm for obtaining Sudoku matrices. Introduced by Geir Dahl concept disjoint pairs of S-permutation matrices [G. Dahl, Permutation matrices related to Sudoku, Linear Algebra and its Applications (430) (2009) 2457–2463] is used in this algorithm. Analyzing the works of G. Dahl and R. Fontana, the question of finding a general formula for counting disjoint pairs of n²×n²$n^2\times n^2$ S-permutation matrices as a function of the integer n$n$ naturally arises. This is an interesting combinatorial problem that deserves its consideration. The present work solves this problem. To do that, the graph theory techniques have been used. It has been shown that to count the number of disjoint pairs of n²×n²$n^2\times n^2$ S-permutation matrices, it is sufficient to obtain some numerical characteristics of the set of all bipartite graphs of the type g=〈_Rg∪_Cg,_Eg〉$g=〈R_g\cup C_g,E_g〉$, where V=_Rg∪_Cg$V=R_g\cup C_g$ is the set of vertices, and _Eg$E_g$ is the set of edges of the graph g$g$, _Rg∩_Cg=0?$R_g\cap C_g=0?$, |_Rg|=|_Cg|=n$\left|R_g\right|=\left|C_g\right|=n$.     

Asymptotic enumeration of some RNA secondary structures

In this paper, we derive recursions of some RNA secondary structures with certain properties under two new representations. Furthermore, by making use of methods of asymptotic analysis and generating functions we present asymptotic enumeration of these RNA secondary structures.     

Possible numbers of ones in 0-1 matrices with a given rank

We determine the possible numbers of ones in a 0-1 matrix with given rank in the generic case and in the symmetric case. There are some unexpected phenomena. The rank 2 symmetric case is subtle.     

Summability matrices and sequences of 0's and 1's

Summary Conditions are given on a nonnegative regular summability matrix A to ensure that for a given number α, 0 ≤ α ≤ 1, there exists a sequence x consisting of 0's and 1's such that Ax converges to α.     

The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool

Efficient codes exist for exactly solving the 0-1 knapsack problem, which is a common primitive structure in relaxation and decomposition techniques for the solution of general models. We suggest moving to a higher primitive level by using the bidimensional knapsack, which can be used to enhance linear programming or Lagrangean type classical relaxations.With the ultimate aim of providing an exact and efficient solution to the bidimensional knapsack problem, we describe here a heuristic approach based on surrogate duality. In particular, we consider the usefulness of a specific preprocessing phase before a possible enumerative phase.Extensive numerical experiments, based on test problems from the literature as well as randomly generated instances, show that our code compares favorably with the GP procedure developed by Gavish and Pirkul for the multidimensional case.     

A new linearization technique for multi-quadratic 0-1 programming problems

We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same.     

Non-singular 0-1 matrices with constant row and column sums

This paper explicitly constructs non-singular 0-1 matrices of dimensions n with constant row and column sum k, subject only to the conditions 0<k<n and (k,n)≠(2,4). An application of such matrices to finite geometries can be found in [1].     

Asymptotic Behaviour of the Number of Labelled Essential Acyclic Digraphs and Labelled Chain Graphs

We provide an asymptotic formula for the number of labelled essential DAGs a_n and show that lim_na_n/a_n=c, where a_n is the number of labelled DAGs and c13.65, which is interesting in the field of Bayesian networks. Furthermore, we present an asymptotic formula for the number of labelled chain graphs.Acknowledgment. I would like to thank Prof. Peter Grabner for his support and very helpful discussions, which where constitutive for this article. I am also thankful to the referees for their comments.This Research was supported by the Austrian Science Fund (FWF), START-Project Y96-MATFinal version received: January 28, 2004     

Asymptotic enumeration theorems for the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs

The asymptotic properties of the numbers of spanning trees and Eulerian trails in circulant digraphs and graphs are studied. Let be a directed circulant graph. Let and be the numbers of spanning trees and of Eulerian trails, respectively. Then

On trees with a maximum proper partial 0-1 coloring containing a maximum matching

I prove that in a tree in which the distance between any two endpoints is even, there is a maximum proper partial 0-1 coloring such that the edges colored by 0 form a maximum matching.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.