On the Vertices of the d-Dimensional Birkhoff Polytope |
| |
Authors: | Nathan Linial Zur Luria |
| |
Affiliation: | 1. Department of Computer Science, Hebrew University, Jerusalem, 91904, Israel
|
| |
Abstract: | Let us denote by Ω n the Birkhoff polytope of n×n doubly stochastic matrices. As the Birkhoff–von Neumann theorem famously states, the vertex set of Ω n coincides with the set of all n×n permutation matrices. Here we consider a higher-dimensional analog of this basic fact. Let $varOmega^{(2)}_{n}$ be the polytope which consists of all tristochastic arrays of order n. These are n×n×n arrays with nonnegative entries in which every line sums to 1. What can be said about $varOmega ^{(2)}_{n}$ ’s vertex set? It is well known that an order-n Latin square may be viewed as a tristochastic array where every line contains n?1 zeros and a single 1 entry. Indeed, every Latin square of order n is a vertex of $varOmega^{(2)}_{n}$ , but as we show, such vertices constitute only a vanishingly small subset of $varOmega^{(2)}_{n}$ ’s vertex set. More concretely, we show that the number of vertices of $varOmega ^{(2)}_{n}$ is at least $(L_{n})^{frac{3}{2}-o(1)}$ , where L n is the number of order-n Latin squares. We also briefly consider similar problems concerning the polytope of n×n×n arrays where the entries in every coordinate hyperplane sum to 1, improving a result from Kravtsov (Cybern. Syst. Anal., 43(1):25–33, 2007). Several open questions are presented as well. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|