Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Author Package file for use with AMS-LaTeX 1.2
\controldates{17-DEC-2004,17-DEC-2004,17-DEC-2004,17-DEC-2004}
 
\RequirePackage[warning,log]{snapshot}
\documentclass{era-l}

\issueinfo{10}{17}{}{2004}
\dateposted{December 24, 2004}
\pagespan{155}{158}
\PII{S 1079-6762(04)00140-4}
\copyrightinfo{2004}{American Mathematical Society}
\revertcopyright

\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsthm,amssymb,latexsym}
\usepackage{epic}
\usepackage{eepic}
\usepackage{xypic}
\usepackage{mathrsfs}

\newtheorem{conjecture}{Conjecture}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\theoremstyle{definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\e}{\ar@{-}}
\newcommand{\n}{*=0{\bullet}}
\newcommand{\ns}{*=0{\star}}

\newcommand{\newop}[1]{\expandafter\def\csname #1\endcsname{\mathop{\rm
#1}\nolimits}}

\newop{des}
\newop{min}


\usepackage{graphicx}

\begin{document}

\title[Counterexamples to the Neggers-Stanley conjecture]
{Counterexamples to the Neggers-Stanley conjecture}
\author{Petter Br\"and\'en}
\address{Department of Mathematics,
Chalmers University of Technology and G\"oteborg University,
S-412~96  G\"oteborg,
Sweden}
\email{branden@math.chalmers.se}
\commby{Sergey Fomin}
\date{August 31, 2004}

\subjclass[2000]{Primary 06A07, 26C10}
\keywords{Neggers-Stanley conjecture, partially ordered set, linear
extension, real roots}


\begin{abstract}
The Neggers-Stanley conjecture  asserts 
that the polynomial counting the linear 
extensions of a labeled finite
partially ordered set  by the number of descents has 
real zeros only. We provide counterexamples to this conjecture. 
\end{abstract}

\maketitle

A finite partially ordered set (\emph{poset}) $P$ of cardinality 
$p$ is said to be \emph{labeled} if its elements are identified with 
the integers  $1,2,\ldots, p$. 
We will use the symbol $\prec$ to denote the 
partial order on~$P$ and $<$ to denote the usual order on the 
integers.    
The {\em Jordan-H\"older set} $\mathcal{L}(P)$ 
is the set of permutations $\pi=(\pi_1,\ldots,\pi_p)$ of~
$[p]\stackrel{\rm def}{=}\{1,2,\ldots, p\}$ 
which encode the linear extensions of~$P$. 
More precisely, $\pi\in\mathcal{L}(P)$ 
if $\pi_i \prec \pi_j$ implies~$i \pi_{i+1}$. 
Let $\des(\pi)$ denote the number of descents in~$\pi$. 
The \emph{$W$-polynomial} of a labeled poset $P$ is defined by 
$$
W(P,t) = \sum_{\pi \in \mathcal{L}(P)}t^{\des(\pi)}.
$$
$W$-polynomials appear naturally in many combinatorial contexts 
\cite{Brenti,Simion,Stanleythesis}, and are connected to Hilbert series 
of the Stanley-Reisner rings of simplicial complexes 
\cite[Section III.7]{Stanleygreen} and algebras with straightening laws 
\cite[Theorem 5.2.]{StanleyHilbert}.

\begin{example} 
Let $P_{2,2}$ be the labeled poset shown in Figure~\ref{fig}. Then 
$$
\mathcal{L}(P_{2,2})=\{(1,3,2,4),(1,3,4,2),(3,1,2,4),(3,1,4,2),(3,4,1,2)\},
$$ 
so $W(P_{2,2},t)=4t+t^2$.
\end{example}

\begin{figure}[h]
\setlength{\unitlength}{10mm}
\equation
P_{2,2}\,=\,\vcenter{\xymatrix@R=14pt@C=14pt{
              2& 4&&\\
              1\e[u]& 3\e[lu]\e[u]&&
          }}
$$
\caption{The poset $P_{2,2}$.}
\label{fig} 
\end{figure}

When $P$ is a $p$-element antichain, 
then $\mathcal{L}(P)$ consists of all permutations of~$[p]$, and 
$W(P,t)$ is the $p$th {\em Eulerian polynomial}. The Eulerian 
polynomials are known \cite{Harper} to have only real zeros. 
In this instance, the \emph{Neggers-Stanley conjecture} holds: 

\begin{conjecture}[Neggers-Stanley] 
\label{NS}
For any finite labeled poset~$P$, 
all zeros of the polynomial $W(P,t)$ are real.
\end{conjecture}

A poset $P$ is \emph{naturally labeled} if 
$i\prec j$ implies~$i