Brunn--Minkowski inequalities for contingency tables and integer flows

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

Authors Alexander Barvinok

Publication date 18 April 2007

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

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

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)

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.

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

Cites work

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

Cited in

(10)

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

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)