## 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 Ω_{n}^{(2)} 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 Ω_{n}^{(2)}'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 Ω_{n}^{(2)}, but as we show, such vertices constitute only a vanishingly small subset of Ω_{n}^{(2)}'s vertex set. More concretely, we show that the number of vertices of Ω_{n}^{(2)} is at least (L_{n})^{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.

Original language | English |
---|---|

Pages (from-to) | 161-170 |

Number of pages | 10 |

Journal | Discrete and Computational Geometry |

Volume | 51 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2014 |

### Bibliographical note

Funding Information:N. Linial was supported by ISF and BSF grants.

## Keywords

- Birkhoff polytope
- Combinatorics
- Latin squares