Brunn--Minkowski inequalities for contingency tables and integer flows

DOI10.1016/J.AIM.2006.07.012zbMATH Open1119.05005arXivmath/0603655OpenAlexW2015081804MaRDI QIDQ876322FDOQ876322

Authors: Alexander Barvinok 

Publication date: 18 April 2007

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

Abstract: Given a non-negative mxn matrix W=(w_ij) and positive integer vectors R=(r_1, >..., r_m) and C=(c_1, ..., c_n), we consider the total weight T(R, C; W) of mxn non-negative integer matrices (contingency tables) D with the row sums r_i, the column sums c_j, and the weight of D=(d_ij) equal to product of w_ij^d_ij. In particular, if W is a 0-1 matrix, T(R, C; W) is the number of integer feasible flows in a bipartite network. We prove a version of the Brunn-Minkowski inequality relating the numbers T(R, C; W) and T(R_k, C_k; W), where (R, C) is a convex combination of (R_k, C_k) for k=1, ..., p.

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

Recommendations

• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Approximately counting integral flows and cell-bounded contingency tables
• Enumerating Contingency Tables via Random Permanents
• Log-concave functions

zbMATH Keywords

contingency tablespermanentlog-concave functionsinteger pointsmatrix scalingBrunn--Minkowski inequalityflow polytopes

Mathematics Subject Classification ID

Contingency tables (62H17) Exact enumeration problems, generating functions (05A15) Inequalities and extremum problems involving convexity in convex geometry (52A40)

Cites Work

• Title not available (Why is that?)
• The concentration of measure phenomenon
• Scaling of matrices to achieve specified row and column sums
• Title not available (Why is that?)
• A course in combinatorics.
• Title not available (Why is that?)
• The Brunn-Minkowski inequality
• Title not available (Why is that?)
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Title not available (Why is that?)
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Testing for independence in a two-way table: New interpretations of the chi-square statistic
• The asymptotic number of non-negative integer matrices with given row and column sums
• The solution of van der Waerden's problem for permanents
• New permanental upper bounds for nonnegative matrices
• A Brunn-Minkowski inequality for the integer lattice
• Scalings of matrices which have prespecified row sums and column sums via optimization
• Counting integer flows in networks
• Enumerating Contingency Tables via Random Permanents
• Random matrices, magic squares and matching polynomials

Cited In (10)

• Asymptotic Estimates for the Number of Contingency Tables, Integer Flows, and Volumes of Transportation Polytopes
• On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \)
• Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons
• Cayley's hyperdeterminant: A combinatorial approach via representation theory
• Random sampling of contingency tables via probabilistic divide-and-conquer
• Bounds on Kronecker coefficients via contingency tables
• Matrices with prescribed row and column sums
• Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
• An approximation algorithm for counting contingency tables
• Lower bounds for contingency tables via Lorentzian polynomials

This page was built for publication: Brunn--Minkowski inequalities for contingency tables and integer flows

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