"Birkhoff–von Neumann polytope"의 두 판 사이의 차이

2020년 11월 13일 (금) 10:37 판

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

@@ 2번째 줄: / 2번째 줄: @@
 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
+Let <math>H_n (r)</math> be the number of <math>n \times n</math> magic squares with line sums equal
-to $r$. The problem to determine $H_n (r)$ appeared early in the twentieth
+to <math>r</math>. The problem to determine <math>H_n (r)</math> appeared early in the twentieth
 century \cite{Ma}. Since then it has attracted considerable attention
 within areas such as combinatorics, combinatorial and computational
@@ 11번째 줄: / 11번째 줄: @@
 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
+positive integer <math>n</math>, the quantity <math>H_n (r)</math> is a polynomial in <math>r</math> of
-degree $(n-1)^2$. More precisely, the following theorem holds.
+degree <math>(n-1)^2</math>. More precisely, the following theorem holds.
 ;begin{theorem} {\rm (Stanley~\cite{St1, St2})}
-For any positive integer $n$ we have
+For any positive integer <math>n</math> we have
 \begin{equation}
@@ 23번째 줄: / 23번째 줄: @@
 \end{equation}
-where $d = n^2 - 3n + 2$ and the $h_i$ are nonnegative integers satisfying
+where <math>d = n^2 - 3n + 2</math> and the <math>h_i</math> are nonnegative integers satisfying
-$h_0 = 1$ and $h_i = h_{d-i}$ for all $i$.
+<math>h_0 = 1</math> and <math>h_i = h_{d-i}</math> for all <math>i</math>.
 \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
+the integers <math>h_i</math> appearing in (\ref{mag0}) satisfy further the inequalities
 \begin{equation}