Facets of the X-ray polytope of doubly stochastic matrices
Abstract
We study the polytope of anti-diagonal X-rays of k x k doubly stochastic matrices, the image of the Birkhoff polytope under the map that sums the entries along each anti-diagonal. Its facets other than the coordinate facets are the minimal joint tail bounds for lattice laws of a sum of two dependent uniform random variables. We give an exact facet criterion in terms of the allowed edges of a tight graph. For rays of the underlying tropical fan, total support of the tight graph suffices for a facet but is not necessary, as an example with k=19 shows. Up to affine functions and positive scaling, the potentials that define a facet form a polytope whose vertices are its rays. Facets propagate by padding and by grid refinement under explicit hypotheses. We give infinite families of facets from no step potential, facets of quadratic height, superpolynomially many facets, and a classification of three-step potentials. Total support of a step potential is characterized by a Hall-type condition on block starts; with computer assistance, total support decides facets of step potentials for k<=26. The facet counts up to k=12 are found directly for k<=3 and, for k>=4, come from an enumeration by a provably complete algorithm; an independent exact recomputation reproduces its ray lists for 5<=k<=12.
Related
- Binary X-rays of doubly stochastic matrices
- A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
- On e-doubly stochastic matrices over hyperbolic (polynomial) systems
- On the facets of the Cayley polytope of Stanley's triangulation
- Facets of nondegeneracy: central type factor groups, Heisenberg representations and Hadamard matrices
BibTeX
@misc{chaudhary2026facets,
title = {{Facets of the X-ray polytope of doubly stochastic matrices}},
author = {Prashant Chaudhary and Kapil Khandelwal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30058},
eprint = {2610.30058},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30058},
}
RIS
TY - UNPB
TI - Facets of the X-ray polytope of doubly stochastic matrices
AU - Prashant Chaudhary
AU - Kapil Khandelwal
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.30058
UR - https://arxiv.org/abs/2610.30058
AB - We study the polytope of anti-diagonal X-rays of k x k doubly stochastic matrices, the image of the Birkhoff polytope under the map that sums the entries along each anti-diagonal. Its facets other than the coordinate facets are the minimal joint tail bounds for lattice laws of a sum of two dependent uniform random variables. We give an exact facet criterion in terms of the allowed edges of a tight graph. For rays of the underlying tropical fan, total support of the tight graph suffices for a facet but is not necessary, as an example with k=19 shows. Up to affine functions and positive scaling, the potentials that define a facet form a polytope whose vertices are its rays. Facets propagate by padding and by grid refinement under explicit hypotheses. We give infinite families of facets from no step potential, facets of quadratic height, superpolynomially many facets, and a classification of three-step potentials. Total support of a step potential is characterized by a Hall-type condition on block starts; with computer assistance, total support decides facets of step potentials for k<=26. The facet counts up to k=12 are found directly for k<=3 and, for k>=4, come from an enumeration by a provably complete algorithm; an independent exact recomputation reproduces its ray lists for 5<=k<=12.
ER -