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

DOI10.1016/j.aim.2009.12.001zbMath1191.15031arXiv0806.1480MaRDI QIDQ962158

Alexander I. Barvinok

Publication date: 6 April 2010

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0806.1480

zbMATH Keywords

entropy; convex optimization; random matrix; asymptotic estimates; 0-1 matrices; integer flows

Mathematics Subject Classification ID

90C25: Convex programming

05B20: Combinatorial aspects of matrices (incidence, Hadamard, etc.)

15A29: Inverse problems in linear algebra

15B52: Random matrices (algebraic aspects)

15B36: Matrices of integers

Related Items

Characterizing optimal sampling of binary contingency tables via the configuration model, The number of graphs and a random graph with a given degree sequence, Analysis of local search landscapes for \(k\)-SAT instances, Random graphs with a given degree sequence, The maximal length of a chain in the Bruhat order for a class of binary matrices, Bootstrapping on undirected binary networks via statistical mechanics, Matrices with prescribed row and column sums, Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes, On the largest size of an antichain in the Bruhat order for \(\mathcal A (2k,k)\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The enumeration of arrays and a generalization related to contingency tables
• Entropy bounds for perfect matchings and Hamiltonian cycles
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Fast uniform generation of regular graphs
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• Hamiltonian cycles in Dirac graphs
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all
• The asymptotic number of non-negative integer matrices with given row and column sums
• Classical complexity and quantum entanglement
• Integration and optimization of multivariate polynomials by restriction onto a random subspace
• Asymptotic enumeration of dense 0-1 matrices with specified line sums
• Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
• Random dense bipartite graphs and directed graphs with specified degrees
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• Two Algorithmic Results for the Traveling Salesman Problem
• Asymptotics and random matrices with row-sum and column sum-restrictions
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Sampling binary contingency tables with a greedy start
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents