Return to Answer

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$. In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$. In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$. Addendum: At least the discrete infinite case is addressed, with generally positive results, in this review and in this older review. The older paper also raises the continuous question but with no results. However, with some more Googling I found this counterexample paper.

Since Gil asks for a reference, a recent one is Unital Quantum Channels - Convex Structure and Revivals of Birkhoff's Theorem, by Mendl and Wolf.

A doubly stochastic matrix can be interpreted as a flow through a directed graph, with unit capacities. (See Unimodular matrix in Wikipedia; I learned about this long ago from Jesus de Loera.) Any such graph has a polytope of flows, called a network flow polytope. Any network flow polytope has integer vertices, because it is a totally unimodular polytope.

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$. In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$. In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$. Addendum: At least the discrete infinite case is addressed, with generally positive results, in this review and in this older review. The older paper also raises the continuous question but with no results. However, with some more Googling I found this counterexample paper.

Since Gil asks for a reference, a recent one is Unital Quantum Channels - Convex Structure and Revivals of Birkhoff's Theorem, by Mendl and Wolf.

A doubly stochastic matrix can be interpreted as a flow through a directed graph, with unit capacities. (See Unimodular matrix in Wikipedia; I learned about this long ago from Jesus de Loera.) Any such graph has a polytope of flows, called a network flow polytope. Any network flow polytope has integer vertices, because it is a totally unimodular polytope.

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$. In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$. In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$.

I am left wondering about two infinite classical versions of Birkhoff's theorem, for the algebras $\ell^\infty(\mathbb{N})$ and $L^\infty([0,1])$. In the former case, one would ask whether any stochastic map that preserves counting measure (even though counting measure is not normalized) is an infinite convex sum of permutations of $\mathbb{N}$. In the latter case, whether any stochastic map that preserve Lebesgue measure is a convex integral of measure-preserving permutations of $[0,1]$. Addendum: At least the discrete infinite case is addressed, with generally positive results, in this review and in this older review. The older paper also raises the continuous question but with no results. However, with some more Googling I found this counterexample paper.

Here also is a more orthodox combinatorial generalization of the Birkhoff theorem, and also another case that I once encountered that is between a generalization and a non-generalization. Since Gil now offers a bounty, maybe it's better to merge this answer with the other one.

A doubly stochastic matrix can be interpreted as a flow through a directed graph, with unit capacities. (See Unimodular matrix in Wikipedia; I learned about this long ago from Jesus de Loera.) Any such graph has a polytope of flows, called a network flow polytope. Any network flow polytope has integer vertices, because it is a totally unimodular polytope.

A totally unimodular polytope is a polytope whose facets have integer equations, and with the property that any maximal, linearly independent collection of facets intersects in an integer point because their matrix has determinant $\pm 1$. In particular the vertices are such intersections, so the vertices are all integral. This is a vast generalization of Birkhoff's theorem that comes from generalizing one of the proofs of Birkhoff's theorem.

Example: An alternating-sign matrix is equivalent to a square ice orientation of a square grid. The square ice orientations can be defined by a network flow, so you obtain an alternating-sign-matrix polytope. The generalized Birkhoff theorem in this case says that every vertex of the polytope is an alternating-sign matrix, in fact that every integer point of the $n$-dilated polytope is a sum of $n$ alternating-sign matrices.

The other case that I encountered was the polytope of fractional perfect matchings of a non-bipartite set with $2n$ elements. By contrast, the Birkhoff polytope is the case of a bipartite set with $n$ elements of each type. By definition, it is the polytope of non-negative weights assigned to the edges of the complete graph on $2n$ vertices, such that the total weight at each vertex is 1. Strictly speaking, the Birkhoff theorem is false; not every vertex is a perfect matching. Instead, all of the vertices are combinations of matched pairs, and odd cycles with weight $\frac12$.

At first glance this looks like bad news for the application of computing a perfect matching or the optimum perfect matching of a graph. Indeed, if instead you take the convex hull of the perfect matchings, the result is a polytope with exponentially many facets. However, a good algorithm exists anyway; there is a version of the simplex algorithm that only ever uses polynomially many of the facets.