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

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

메타데이터

위키데이터

ID : Q4916482

Spacy 패턴 목록

[{'LOWER': 'birkhoff'}, {'LEMMA': 'polytope'}]