Four Questions on Birkhoff Polytope

We ask several questions on the structure of the polytope P_n of doubly stochastic n 2 n matrices, known as a Birkhoff polytope. We discuss the volume of P_n, the work of the simplex method, and the mixing of random walks on P_n.     

On the Vertices of the d-Dimensional Birkhoff Polytope

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.     

Norm Bounds for Ehrhart Polynomial Roots

M. Beck et al. found that the roots of the Ehrhart polynomial of a d-dimensional lattice polytope are bounded above in norm by 1+(d+1)!. We provide an improved bound which is quadratic in d and applies to a larger family of polynomials.     

Polynomial algebra for Birkhoff interpolants

We introduce a unifying formulation of a number of related problems which can all be solved using a contour integral formula. Each of these problems requires finding a non-trivial linear combination of possibly some of the values of a function f, and possibly some of its derivatives, at a number of data points. This linear combination is required to have zero value when f is a polynomial of up to a specific degree p. Examples of this type of problem include Lagrange, Hermite and Hermite–Birkhoff interpolation; fixed-denominator rational interpolation; and various numerical quadrature and differentiation formulae. Other applications include the estimation of missing data and root-finding.     

三角多项式类中的Birkhoff型三角插值

本文在三角多项式类中讨论了2π周期函数的一类Birkhoff型等距结点的三角插值问题,给出了此问题有解的充要条件,并构造出插值基.     

Robust Hadamard Matrices,Unistochastic Rays in Birkhoff Polytope and Equi-Entangled Bases in Composite Spaces

We study a special class of (real or complex) robust Hadamard matrices, distinguished by the property that their projection onto a 2-dimensional subspace forms a Hadamard matrix. It is shown that such a matrix of order n exists, if there exists a skew Hadamard matrix or a symmetric conference matrix of this size. This is the case for any even \(n\le 20\), and for these dimensions we demonstrate that a bistochastic matrix B located at any ray of the Birkhoff polytope, (which joins the center of this body with any permutation matrix), is unistochastic. An explicit form of the corresponding unitary matrix U, such that \(B_{ij}=|U_{ij}|^2\), is determined by a robust Hadamard matrix. These unitary matrices allow us to construct a family of orthogonal bases in the composed Hilbert space of order \(n \times n\). Each basis consists of vectors with the same degree of entanglement and the constructed family interpolates between the product basis and the maximally entangled basis. In the case \(n=4\) we study geometry of the set \({\mathcal U}_4\) of unistochastic matrices, conjecture that this set is star-shaped and estimate its relative volume in the Birkhoff polytope \({\mathcal B}_4\).     

Smooth Fano Polytopes Whose Ehrhart Polynomial Has a Root with Large Real Part

The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this paper, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.     

The Contact Polytope of the Leech Lattice

The contact polytope of a lattice is the convex hull of its shortest vectors. In this paper we classify the facets of the contact polytope of the Leech lattice up to symmetry. There are 1,197,362,269,604,214,277,200 many facets in 232 orbits.     

The topology of Birkhoff varieties

Our main theorem is that the inclusion of any Birkhoff subvariety in an affine flag variety is a homotopy equivalence. We also construct analogues of tubular neighborhoods for Birkhoff and Schubert varieties in affine or classical flag varieties.     

The Reflexive Dimension of a Lattice Polytope

The reflexive dimension refldim(P) of a lattice polytope P is the minimal integer d so that P is the face of some d-dimensional reflexive polytope. We show that refldim(P) is finite for every P, and give bounds for refldim(kP) in terms of refldim(P) and k. Received July 2, 2004     

The diameter of the acyclic Birkhoff polytope

In this work we give an interpretation of vertices and edges of the acyclic Birkhoff polytope, T_n=Ω_n(T), where T is a tree with n vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph G(T_n).     

The Birkhoff integral and the property of Bourgain

In this paper we study the Birkhoff integral of functions f:X defined on a complete probability space (,,) with values in a Banach space X. We prove that if f is bounded then its Birkhoff integrability is equivalent to the fact that the set of compositions of f with elements of the dual unit ball Z_f={x*,f:x*B_X*} has the Bourgain property. A non necessarily bounded function f is shown to be Birkhoff integrable if, and only if, Z_f is uniformly integrable and has the Bourgain property. As a consequence it turns out that the range of the indefinite integral of a Birkhoff integrable function is relatively norm compact. We characterize the weak Radon-Nikodým property in dual Banach spaces via Birkhoff integrable Radon-Nikodým derivatives. We also point out that a recently introduced notion of unconditional Riemann-Lebesgue integrability coincides with the notion of Birkhoff integrability. Some other applications are given.Mathematics Subject Classification (2000): 28B05, 46B22, 46G10Partially supported by the research grant BFM2002-01719 of MCyT (Spain). The second author was supported by a FPU grant of MECD (Spain).Acknowledgement We gratefully thank Gabriel Vera for lively discussions about some material considered in this paper. We also thank the referee for helpful suggestions that have improved the exposition of this work.     

The Integer Hull of a Convex Rational Polytope

Given $A\in\Z^{m\times n}$ and $b\in\Z^m$, we consider the integer program $\max \{cx\vert Ax=b;x\in\N^n\}$ and provide an {\it equivalent} and {\it explicit} linear program $\max \{\widehat{\xcc}q\vert \m q=r;q\geq 0\}$, where $\m,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $\p=\{x\in\R^n\vert Ax=b;x\geq0\}$. All strong valid inequalities can be obtained from the generators of a convex cone whose definition is explicit in terms of $\m$.     

Decomposing the Secondary Cayley Polytope

The vertices of the secondary polytope of a point configuration correspond to its regular triangulations. The Cayley trick links triangulations of one point configuration, called the Cayley polytope, to the fine mixed subdivisions of a tuple of point configurations. In this paper we investigate the secondary polytope of this Cayley polytope. Its vertices correspond to all regular mixed subdivisions of a tuple of point configurations. We demonstrate that it equals the Minkowski sum of polytopes, which we call mixed secondary polytopes, whose vertices correspond to regular-cell configurations. Received October 1, 1998, and in revised form July 23, 1999.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

Computing the Ehrhart quasi-polynomial of a rational simplex

We present a polynomial time algorithm to compute any fixed number of the highest coefficients of the Ehrhart quasi-polynomial of a rational simplex. Previously such algorithms were known for integer simplices and for rational polytopes of a fixed dimension. The algorithm is based on the formula relating the th coefficient of the Ehrhart quasi-polynomial of a rational polytope to volumes of sections of the polytope by affine lattice subspaces parallel to -dimensional faces of the polytope. We discuss possible extensions and open questions.

     

Ehrhart polynomials of cyclic polytopes

The Ehrhart polynomial of an integral convex polytope counts the number of lattice points in dilates of the polytope. In (Coefficients and roots of Ehrhart polynomials, preprint), the authors conjectured that for any cyclic polytope with integral parameters, the Ehrhart polynomial of it is equal to its volume plus the Ehrhart polynomial of its lower envelope and proved the case when the dimension d=2. In our article, we prove the conjecture for any dimension.