Birkhoff–von Neumann polytope

introduction

A magic square is a square matrix with nonnegative integer entries having all line sums equal to each other, where a line is a row or a column. Let $H_n (r)$ be the number of $n \times n$ magic squares with line sums equal to $r$. The problem to determine $H_n (r)$ appeared early in the twentieth century \cite{Ma}. Since then it has attracted considerable attention within areas such as combinatorics, combinatorial and computational commutative algebra, discrete and computational geometry, probability and statistics \cite{ADG, BP, DG, Eh, JvR, Sp, St1, St2, St4, St5, SS}. It was conjectured by Anand, Dumir and Gupta \cite{ADG} and proved by Ehrhart \cite{Eh} and Stanley \cite{St1} (see also \cite[Section I.5]{St4} and \cite[Section 4.6]{St5}) that for any fixed positive integer $n$, the quantity $H_n (r)$ is a polynomial in $r$ of degree $(n-1)^2$. More precisely, the following theorem holds.

begin{theorem} {\rm (Stanley~\cite{St1, St2})}

For any positive integer $n$ we have

\begin{equation} \sum_{r \ge 0} \, H_n (r) \, t^r = \frac{h_0 + h_1 t + \cdots + h_d t^d} {(1 - t)^{(n-1)^2 + 1}}, \label{mag0} \end{equation}

where $d = n^2 - 3n + 2$ and the $h_i$ are nonnegative integers satisfying $h_0 = 1$ and $h_i = h_{d-i}$ for all $i$. \label{thm0}

It is the first conjecture stated in \cite{St4} (see Section I.1 there) that the integers $h_i$ appearing in (\ref{mag0}) satisfy further the inequalities

\begin{equation} h_0 \le h_1 \le \cdots \le h_{\lfloor d/2 \rfloor}. \label{mag1} \end{equation}

expositions

• http://www.math.binghamton.edu/dennis/Birkhoff/

computational resource

• https://drive.google.com/file/d/0B8XXo8Tve1cxRDRnNGlwcGZLN0E/view
• http://www.math.binghamton.edu/dennis/Birkhoff/polynomials.html

articles

• Christos A. Athanasiadis, Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, arXiv:math/0312031 [math.CO], December 01 2003, http://arxiv.org/abs/math/0312031