Effective poset inequalities
We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner--Wachs inequality and generalize it to inequalities on order polynomials and their $q$-analogues via direct injections and FKG inequalities. Second, we give an injective proof of the Sidorenko inequality with computational complexity significance, namely that the difference is in $\#P$. Third, we generalize the Sidorenko inequality to posets with small chain intersections and give complexity theoretic applications.
\section{Introduction}

\medskip

\subsection{Foreword}\label{ss:intro-foreword}
There are two schools of thought on what to do when an \defng{interesting
combinatorial inequality} is established.  The first approach would
be to treat it as a tool to prove a desired result.  The inequality
can still be sharpened or generalized as needed, but this effort is
aimed with applications as the goal and not about the inequality per se.

The second approach is to treat the inequality as a result of importance
in its own right.  The emphasis then shifts to finding the ``right proof''
in an attempt to understand, refine or generalize it.  This is where the
nature of the inequality intervenes --- when both sides count combinatorial
objects, the desire to relate these objects is overpowering.

The inequality can be made \defna{effective} \hskip.03cm
in several different ways.   A \defng{direct injection}
can give it a combinatorial interpretation
for the difference or prove the equality conditions.
Such an injection can also be a work of art,
inspiring and thought-provoking in the best case.
Alternatively, a \defng{technical proof} (say, probabilistic or algebraic),
can establish tools for generalizations out of reach by direct combinatorial
arguments.

Both types of proof are most impactful when presented in combination.
Making comparisons between different approaches can lead to further
results, new open problems, and is the source of wonder of the beauty
and diversity of mathematics.



\medskip

As the reader must have guessed, we aim to make effective several
celebrated combinatorial inequalities for the numbers of
linear extensions of finite posets:

\smallskip

\qquad $\circ$ \ the \defn{Bj\"orner--Wachs inequality},

\smallskip

\qquad $\circ$ \ the \defn{Sidorenko inequality}, and

\smallskip

\qquad $\circ$ \ the \defn{generalized Stanley inequality}.

\smallskip

\noindent
Although there is a certain commonality of tools and approaches,
our investigation of these inequalities are largely independent,
united by the goal of being effective.  In addition to injections,
we also use \defng{probabilistic} and \defng{algebraic tools}, with some
curious combinatorial twists.


\smallskip

\subsection{Bj\"orner--Wachs inequality}\label{ss:intro-HP}

Let \. $P=(X,\prec)$ \. be a poset with \. $|X|=n$ \. elements.
For each element \hskip.03cm $x \in X$, let \.
$B(x) := \big\{y \in X \. : \. y \succcurlyeq x  \big\}$ \.
be the \defn{upper order ideal} generated by~$x$, and let \. $b(x):=|B(x)|$.

A \defn{linear extension} of $P$ is a bijection \. $f: X \to [n]=\{1,\ldots,n\}$,
such that
\. $f(x) < f(y)$ \. for all \. $x \prec y$.
Denote by \hskip.03cm $\Ec(P)$ \hskip.03cm the set of linear extensions of $P$,
and let \. $e(P):=|\Ec(P)|$.

\smallskip

\begin{thm}[{\rm Bj\"orner and Wachs~\cite[Thm~6.3]{BW89}}{}]\label{t:HP}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.
In the notation above, we have:
\begin{equation}\label{eq:HP}
e(P) \ \geq  \  \. n! \.\cdot \. \prod_{x \in X} \, \frac{1}{b(x)}\,.
\end{equation}
\end{thm}

\smallskip

This inequality was popularized by Stanley who stated it without proof
or a reference in \cite[Exc.~3.57]{Sta-EC}.\footnote{Richard Stanley
informed us that he indeed took it from~\cite{BW89} (personal communication, March 27, 2022).}
When the poset is a tree rooted at the
minimal element, the inequality in the theorem is an equality known
in the literature as the \defn{hook-length formula for trees}.  A
variation on the classical \defn{hook-length formulas} for straight and
shifted Young diagrams, this case is usually attributed to Don Knuth (1973),
see e.g.~\cite{Bea,SY}.  Although for other families of poset the lower bound
on~$e(P)$ given by~\eqref{eq:HP} is relatively weak, nothing better is
known in full generality, see e.g.~\cite{BP,MPP-asy,Pak-case}.

\smallskip

We start by recalling the original direct injective proof by Bj\"orner and Wachs
of the inequality~\eqref{eq:HP}. This allows us to prove that the inequality is in~${\textsc{\#P}}$
(Theorem~\ref{t:HP-SP}).  We then obtain the following extension
of Theorem~\ref{t:HP}.

\smallskip

Let \hskip.03cm $[k]:=\{1,\ldots,k\}$.
For an integer \hskip.03cm $t\ge 1$, denote by \. $\Omega(P,t)$ \. the number of
order preserving maps \. $g: X\to [t]$, i.e.\ maps which satisfy
\. $g(x)\le g(y)$ \. for all \. $x \prec y$.  This is the \defn{order polynomial}
corresponding to poset~$P$, see e.g.~\cite[$\S$3.12]{Sta-EC}.

\smallskip


\begin{thm}\label{thm:HP order poly}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.  Then,
for every \hskip.03cm $t\in \mathbb N$, we have:
\begin{equation}\label{eq:OP-HP}
\Omega(P,t) \ \geq \ t^r \hskip.03cm (t+1)^{n-r} \, \prod_{x \in X} \. \frac{1}{b(x)}\,,
\end{equation}
where $r$ is the number of maximal elements of~$P$.
\end{thm}

\smallskip

Let us note that
\begin{equation}\label{eq:OP-asy}
\Omega(P,t) \ \sim \ \frac{e(P)\, t^n}{n!}   \quad \text{as} \ \ \ t \to \infty\hskip.03cm.
\end{equation}
Thus, Theorem~\ref{thm:HP order poly} implies Theorem~\ref{t:HP}.
Note also that \. $\Omega(P,t) \hskip.03cm = \hskip.03cm \Omega(P^\ast,t)$, where \hskip.03cm $P^\ast=(X, \prec^\ast)$ \hskip.03cm
is the poset where relations are reversed:  \hskip.03cm $x\prec y \ \Leftrightarrow \ y \prec^\ast x$.
Thus, the theorem holds when maximal elements are replaced with minimal elements.


The tools we use to establish Theorem~\ref{thm:HP order poly} are based on
\defng{Shepp's lattice}, and are extremely
far-reaching.  They allows us to establish a variety of inequalities on the order polynomial
as well as their $q$-analogues.
Notably, we establish the asymptotic version of \defng{Graham's conjecture}
(Conjecture~\ref{conj:Graham}) via the following \defng{strict log-concavity} \hskip.03cm of the
order polynomial:


\smallskip

\begin{thm}[{\rm See Theorem~\ref{thm:log-concave} and  Theorem~\ref{thm:log-concave-strict}}{}]
\label{thm:log-concave-intro}
	Let $P=(X,\prec)$ be a finite poset.
	Then, for every integer \hskip.03cm $t \geq 2$, we have:
	\[ \Omega(P,t)^2  \  > \ \Omega(P,t+1) \. \cdot\.  \Omega(P,t-1).\]
\end{thm}

\smallskip


Our next result is a general lower bound on the order polynomial strengthening the
asymptotic formula~\eqref{eq:OP-asy}.

\smallskip


\begin{thm}\label{thm:order_le}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.  Then,
for every \hskip.03cm $t\in \mathbb N$, we have:
\begin{equation}\label{eq:OP-gen}
\Omega(P,t) \ \geq \ \frac{e(P)\, t^n}{n!}\..
\end{equation}
\end{thm}


\smallskip

Our proof of Theorem~\ref{thm:order_le} uses a direct injection.  Among other
applications of this approach, see the equality conditions in Corollary~\ref{c:OP2-equality}.

\smallskip

Since the Bj\"orner--Wachs inequality~\eqref{eq:HP} can be rather weak
in various special cases, neither of Theorems~\ref{thm:HP order poly} and~\ref{thm:order_le}
implies another (see Example~\ref{e:OP-Stanley}).
In a different direction, inequality~\eqref{eq:OP-gen}
strengthens the trivial inequality
\begin{equation}\label{eq:OP-gen-easy}
\Omega(P,t) \ \geq \ e(P) \cdot \binom{t}{n}
 \ = \ \frac{e(P)\,\. t\hskip.03cm (t-1)\cdots (t-n+1)}{n!}\..
\end{equation}
Here the RHS counts the number of injections \. $f: X\to [t]$,
which are naturally mapped onto~$\Ec(P)$.  Note that~\eqref{eq:OP-gen}
agrees with~\eqref{eq:OP-gen-easy} in the leading term given also by~\eqref{eq:OP-asy},
but is sharper in the second term of the asymptotics.

Finally, there is a remarkably simple proof of the Bj\"orner--Wachs inequality
by Vic Reiner, via extension of the inequality to its $q$-analogue
(Theorem~\ref{t:HP-q}).  We also use our tools in~$\S$\ref{ss:q-analogue-our}
to obtain new inequalities for the \defng{$q$-order polynomial}.

\smallskip

\subsection{Sidorenko inequality} \label{ss:intro-sid}
Below we give an equivalent but somewhat nonstandard reformulation
of the \defng{Sidorenko inequality} that makes it amenable for generalization.
A more traditional version is given in Section~\ref{s:sid}.

\smallskip

A \emph{chain} in a poset \. $P=(X,\prec)$ \. is a subset \. $\{x_1,\ldots,x_\ell\} \subseteq X$, such
that \. $x_1 \prec x_2 \prec \ldots \prec x_\ell\hskip.03cm.$ Denote by \hskip.03cm $\mathcal C(P)$ \hskip.03cm the
set of chains in~$P$.

\smallskip

\begin{thm}[{\rm Sidorenko~\cite{Sid}}]\label{t:sid}
Let \. $P=(X,\prec)$ \. and \. $Q=(X,\prec')$ \. be two posets on the same set
with \. $|X|=n$ \. elements.  Suppose
\begin{equation}\label{eq:sid-chain-condition}
\bigl|C \cap C'\bigr| \. \le \. 1 \quad \text{for all} \ \ C\in \mathcal C(P), \ C' \in \mathcal C(Q).
\end{equation}
Then:
\begin{equation}\label{eq:sid}
e(P) \. e(Q)\, \ge \, n!
\end{equation}
\end{thm}

\smallskip
Natural examples of posets \hskip.03cm $(P,Q)$ \hskip.03cm as in the theorem
are the \defn{permutation posets} \hskip.03cm $\bigl(P_\sigma, P_{\overline \sigma}\bigr)$,
where \hskip.03cm $P_\sigma=([n],\prec)$ \hskip.03cm is defined as
$$
i\prec j \quad \Longleftrightarrow\quad  i<j \ \ \text{and} \ \ \sigma(i)<\sigma(j)\,, \quad \text{for all} \ \ i,j\in [n].
$$
and \.  $\overline{\sigma}:=\bigl(\sigma(n),\ldots,\sigma(1)\bigr)$.
In this case \hskip.03cm $P_{\sigma}$ \hskip.03cm is a \defng{$2$-dimensional poset}, and
\hskip.03cm $P_{\overline \sigma}$ \hskip.03cm is its \defng{plane dual}.

Sidorenko's original proof used combinatorial optimization and
proved also equality conditions for~\eqref{eq:sid}, see~$\S$\ref{ss:sid-proof}.
In~\cite{BBS}, the authors gave an easy reduction to a special
case of the (still open) \defng{Mahler conjecture} for \defng{convex corners}.
That special case was resolved earlier by Saint-Raymond~\cite{StR},
and was reproved and further extended in a series of papers, see \cite{AASS,BBS}
for the context and the references.

\smallskip

In this paper we give a direct injective proof of the Sidorenko inequality~\eqref{eq:sid},
which allows us to prove that the inequality is in~${\textsc{\#P}}$ (Theorem~\ref{t:sid-SP}).
This completely resolves the open problem Morales and the last two authors in \cite{MPP}
of finding a combinatorial proof of~\eqref{eq:sid}.  Although presented differently, our 
injection likely coincides with an injection of Gaetz and Gao~\cite{GG1}, see~$\S$\ref{ss:finrem-sid}; 
the latter was discovered independently and generalized to other Coxeter groups.  

\smallskip

Our proof can also be extended to give the following generalization of Theorem~\ref{t:sid}.

\smallskip

\begin{thm}\label{t:sid-gen}
Let \. $P=(X,\prec)$ \. and \. $Q=(X,\prec')$ \. be two posets on the same set
with \. $|X|=n$ \. elements.  Suppose
$$
\bigl|C \cap C'\bigr| \. \le \. k \quad \text{for all} \ \ C\in \mathcal C(P), \ C' \in \mathcal C(Q).
$$
Then:
\begin{equation}\label{eq:sid-gen}
e(P) \. e(Q)\, \ge \,  \frac{n!}{k^{n-k}\. k!} \..
\end{equation}
\end{thm}

\smallskip

The proof, examples and applications of this result are given in Section~\ref{s:sid}.


\smallskip

\subsection{Stanley inequality}\label{ss:intro-Sta}
We start with the following inspiring \defn{Stanley inequality}:

\smallskip

\begin{thm}[{\rm Stanley~\cite{Sta-AF}}{}]\label{t:Sta}
Let \. $P=(X,\prec)$ \. be a poset on \. $|X|=n$ \. elements.  For
an element \. $x\in X$ \. and integer \. $1\le a \le n$, let \.
$\Ec(P,x,a)$ \. be the set of linear extensions \. $f\in \Ec(P)$ \. such
that \. $f(x)=a$.  Denote by \. $\textrm{\em N}(P, x,a):=\bigl|\Ec(P, x,a)\bigr|$ \.
the number of such linear extensions.   Then:
\begin{equation}\label{eq:Sta}
\textrm{\em N}(P, x,a)^2 \, \ge \, \textrm{\em N}(P, x,a+1) \.\cdot \.  \textrm{\em N}(P, x,a-1).
\end{equation}
\end{thm}

\smallskip

Stanley's original proof of this result is via reduction to the classical
and very deep \emph{Alexandrov--Fenchel} (AF-) \emph{inequality} in convex geometry.
While the latter has several proofs, see references in~\cite[$\S$7.1]{CP2},
none are elementary and direct even in the case of convex polytopes.
With the aim to prove \eqref{eq:Sta} by an elementary argument, the (somewhat
technical) proof in~\cite{CP} uses nothing but linear algebra.  Finding
a direct injective proof is a major open problem (see~$\S$\ref{ss:finrem-GP-injection}).

In the absence of an injective proof, the \defng{equality conditions} can become
\emph{more difficult} than the original inequality, cf.~$\S$\ref{ss:finrem-vanishing}.
This is famously the
case for  the AF-inequality and many of its consequences.  For the Stanley
inequality, the equality conditions were discovered recently by
Shenfeld and van Handel~\cite{SvH}, by a deep geometric argument.

Fortunately, part of the equality conditions called the
\defng{vanishing conditions}, are completely combinatorial.
Denote by \hskip.03cm $\ell(x) := \bigl|\{y \in X\,{}:\,{}y\preccurlyeq x\}\bigr|$ \hskip.03cm and \hskip.03cm
$b(x) := \bigl|\{y \in X\,{}:\,{}y\succcurlyeq x\}\bigr|$ \hskip.03cm the sizes of lower
and upper ideals of \hskip.03cm $x\in X$, respectively.

\smallskip

\begin{thm}[{\rm Shenfeld and van Handel~\cite[Lemma~15.2]{SvH}}] \label{t:SvH-vanish}
Let \. $P=(X,\prec)$ \. be a poset on \. $|X|=n$ \. elements,
let \hskip.03cm $x\in X$ \hskip.03cm and \hskip.03cm $1\le a \le n$.  Then \.
$\textrm{\em N}(P, x,a)>0$ \. \underline{if and only if} \. $\ell(x)\le a$ \. and \. $b(x)\le n-a+1$.
\end{thm}

\smallskip

Note that by the Stanley inequality, if \. $\textrm{N}(P, x,a)=0$, then \. $\textrm{N}(P, x,a+ 1)=0$ or \.$\textrm{N}(P, x,a- 1)=0$ ,
so whenever the conditions in the theorem are not satisfied the equation~\eqref{eq:Sta} is
an equality.  We can now define the \hskip.03cm \defn{generalized Stanley inequality}.

\smallskip

\begin{thm}[{\rm Stanley~\cite{Sta-AF}}{}]\label{t:Sta-gen}
Let \. $P=(X,\prec)$ \. be a poset on \. $|X|=n$ \. elements.
Fix elements \. $x,z_1,\ldots,z_k\in X$ \. and integers \. $a,c_1,\ldots,c_k\in [n]$;
we write \. ${\textbf{z}} =(z_1,\ldots,z_k)$ \. and \. $\textbf{\textbf{c}} =(c_1,\ldots,c_k)$.
Let \.
$\Ec_{{\textbf{z}}\hskip.03cm\emph{\textbf{\textbf{c}}}}(P,x,a)$ \. be the set of linear extensions \. $f\in \Ec(P)$ \. such
that \. $f(x)=a$ \. and \. $f(z_i)=c_i$, for all \. $1\le i \le k$.
Denote by \. $\textrm{\em N}_{{\textbf{z}}\hskip.03cm\textbf{\textbf{c}}}(P, x,a):=\bigl|\Ec_{{\textbf{z}}\hskip.03cm\textbf{\textbf{c}}}(P,x,a)\bigr|$ \.
the number of such linear extensions. Then:
\begin{equation}\label{eq:Sta-gen}
\textrm{\em N}_{{\textbf{z}}\hskip.03cm\textbf{\textbf{c}}}(P, x,a)^2 \, \ge \, \textrm{\em N}_{{\textbf{z}}\hskip.03cm\textbf{\textbf{c}}}(P, x,a+1) \.\cdot \.  \textrm{\em N}_{{\textbf{z}}\hskip.03cm\textbf{\textbf{c}}}(P, x,a-1).
\end{equation}
\end{thm}

\medskip


We can now state the \defng{vanishing conditions} for the generalized Stanley inequality.
Without loss of generality, we can assume that numbers~$\textbf{\textbf{c}}$ are in increasing order,
in which case we can assume that elements~${\textbf{z}}$ form a chain.
Let \hskip.03cm $x,y\in X$ \hskip.03cm be two poset elements such that \. $x\prec y$.
Define \. $h(x,y) \hskip.03cm := \hskip.03cm \#\{ z\in P, \text{ s.t. } x\prec z\prec y\}$.

\smallskip

\begin{thm}\label{t:vanish}
Let \. $P=(X,\prec)$ \. be a poset on \. $|X|=n$ \. elements.
Fix elements \. $u_1 \prec\ldots \prec u_k\in X$ \. and integers \. $1\le a_1 < \ldots < a_k \le n$;
we write \. $\textbf{\textit{u}} =(u_1,\ldots,u_k)$ \. and \. $\textbf{\textbf{a}} =(a_1,\ldots,a_k)$.
Let \.
$\Ec(P,\textbf{\textit{u}}, \textbf{{\textit{a}}})$ \. be the set of linear extensions \. $f\in \Ec(P)$ \. such
that \. $f(u_i)=a_i$, for all \. $1\le i \le k$.
Then \. $\bigl|\Ec(P, \textbf{\textit{u}}, \textbf{{\textit{a}}})\bigr| > 0$ \, \underline{if and only if}
\begin{equation}\label{eq:Sta-gen-vanish}
\aligned
& \ell(u_i)\. \le \. a_i \.,  \quad b(u_i)\le n-a_i+1\,, \quad \  \text{for all} \quad 1\.\le \. i \. \le \. k\hskip.03cm, \ \ \, \text{and} \\
& a_j \. - \. a_i \, > \, h(u_i,u_j) \quad \  \text{for all} \quad 1\.\le \. i \. < \. j \. \le \. k\hskip.03cm.
\endaligned
\end{equation}
\end{thm}

\smallskip

In Theorem~\ref{t:gen-Stanley-unique}, we also prove the \defng{uniqueness conditions}
for the problem, i.e.\ necessary and sufficient conditions for \.
$\bigl|\Ec(P, \textbf{\textit{u}}, \textbf{{\textit{a}}})\bigr| = 1$.  We postpone the statement until~$\S$\ref{ss:restricted-unique}.

\smallskip

\subsection{Complexity implications}\label{ss:intro-CS}
We assume the reader is familiar with basic \defna{Computational Complexity},
and refer to standard textbooks \cite{AB,MM,Pap} for definitions and notation.

\smallskip

Recall the \defng{counting complexity class} \. ${\textsc{\#P}}$ \. of functions
which count the number of objects whose membership is decided in
polynomial time.  Let \. ${\textsc{GapP}}={\textsc{\#P}}-{\textsc{\#P}}$ \. be the closure of~${\textsc{\#P}}$
under subtraction, see e.g.~\cite{For}.  Finally,
let \hskip.03cm ${\textsc{GapP}}_{\ge 0} := {\textsc{GapP}} \cap \{u\ge 0\}$.

Clearly, \. ${\textsc{\#P}}\subseteq {\textsc{GapP}}_{\ge 0}$\., but it remains open whether this
inclusion is proper.  For example, the \emph{Kronecker coefficients} \hskip.03cm
$g(\lambda,\mu,\nu) \in {\textsc{GapP}}_{\ge 0}$. It is not known whether $g(\cdot)\in {\textsc{\#P}}$,
and this remains a major open problem in Algebraic Combinatorics,
see e.g.~\cite{PP}.

\smallskip

As before, let \. $P = (X,\prec)$ \. be a poset on \hskip.03cm $n$ \hskip.03cm elements.
Clearly, the function \hskip.03cm $e: P\to e(P)$ \hskip.03cm is in ${\textsc{\#P}}$, and is famously
\hskip.03cm ${\textsc{\#P}}$-complete~\cite{BW}. In fact, the function \hskip.03cm $e(\cdot)$ \hskip.03cm is \hskip.03cm ${\textsc{\#P}}$-complete even
when restricted to permutation posets  \hskip.03cm $P_\sigma$, $\sigma \in S_n$ and posets
of height two, see~\cite{DP}.  Define
\begin{equation}\label{eq:HP-function}
\xi(P) \, := \, e(P) \.\cdot\. \prod_{x \in X} b(x) \, -  \,  \. n!
\end{equation}
Observe that \. $\xi\in {\textsc{GapP}}_{\ge 0}$ \. by the definition and
the  Bj\"orner--Wachs inequality~\eqref{eq:HP}.  In fact, the injective
proof of~\eqref{eq:HP} can be used to obtain the following
effective version of the inequality:

\begin{thm} \label{t:HP-SP}
The function \. $\xi: P \to \mathbb N$ \. defined by~\eqref{eq:HP-function} \hskip.03cm is in~$\hskip.03cm{\textsc{\#P}}$.
\end{thm}

\smallskip

Similarly, define \. ${\zeta}: \hskip.03cm P\times \mathbb N \hskip.03cm \to \mathbb N$
\begin{equation}\label{eq:OP-function}
{\zeta}(P,t) \, := \, \Omega(P,t) \. n! \, -  \,  e(P) \. t^n\..
\end{equation}
We can now give an effective version of~\eqref{eq:OP-gen}:


\smallskip

\begin{thm} \label{t:OP-SP}
The function \. ${\zeta}: P \to \mathbb N$ \. defined by~\eqref{eq:OP-function} \hskip.03cm is in~$\hskip.03cm{\textsc{\#P}}$.
\end{thm}


For every $\sigma\in S_n$, let \hskip.03cm $\eta: S_n \to \mathbb Z$ \hskip.03cm be defined
as follows:
\begin{equation}\label{eq:Sid-function}
\eta(\sigma)\, := \, e(P_\sigma) \. e\bigl(P_{\overline{\sigma}}\bigr)  \, -  \,  \. n!
\end{equation}
Observe that \. $\eta \in {\textsc{GapP}}_{\ge 0}$ \. by the definition and the
Sidorenko inequality~\eqref{eq:sid}. In fact, our injective
proof of~\eqref{eq:sid} can be used to obtain the following result:

\smallskip

\begin{thm} \label{t:sid-SP}
The function \. $\eta: S_n \to \mathbb N$ \. defined by~\eqref{eq:Sid-function} \hskip.03cm is in~$\hskip.03cm{\textsc{\#P}}$.
\end{thm}

\smallskip

For the vanishing conditions of the generalized Stanley inequality, the implications
are completely straightforward:

\smallskip

\begin{cor}  \label{cor:Sta-gen-vanish-poly}
In the conditions of Theorem~\ref{t:vanish}, deciding
whether \. $\bigl|\Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})\bigr| > 0$ \.\hskip.03cm is in $\hskip.03cm{\textsc{P}}$.
Moreover, when \. $\bigl|\Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})\bigr| > 0$, a linear
extension \. $f\in \Ec(P,\textbf{\textit{u}}, \textbf{{\textit{a}}})$ \. can be found in polynomial time.
\end{cor}

\smallskip

We conclude with a corollary of Theorem~\ref{t:gen-Stanley-unique}.

\smallskip

\begin{cor}  \label{cor:Sta-gen-uniqueness-poly}
In the conditions of Theorem~\ref{t:vanish}, deciding
whether \. $\bigl|\Ec(P,\textbf{\textit{u}}, \textbf{{\textit{a}}})\bigr| = 1$ \.\hskip.03cm is in $\hskip.03cm{\textsc{P}}$.
\end{cor}


\smallskip

\subsection{Structure of the paper}
The paper is written in a straightforward manner, as we devote different sections to
proofs of different results.  These proofs are completely independent and
largely self-contained.  We are hoping they will appeal to a diverse
readership.

\smallskip

We start with a short Section~\ref{s:notation}, where give some basic
notation used throughout the paper.
In Section~\ref{s:injective}, we recall the original direct injective proof of the
Bj\"orner--Wachs inequality~\eqref{eq:HP} via direct injection and then
prove Theorem~\ref{t:HP-SP}.  Here we introduce promotions of linear extensions,
a tool which appears repeatedly throughout the paper.

In a lengthy Section~\ref{s:OP-induction}, we use Shepp's lattice
to prove Theorem~\ref{thm:log-concave-intro} and other inequalities
for the order polynomial.  The second half of this section is
motivated by connection and applications to the \defng{Kahn--Saks Conjecture}
(Conjecture~\ref{conj:KS-mon}) and the \defng{Graham Conjecture}
(Conjecture~\ref{conj:Graham}), as we prove special cases of both of them.

In the next Section~\ref{s:q-analogue}, we present
an elegant proof by Reiner of the Bj\"orner--Wachs inequality.  We then
prove a $q$-analogue of \defng{Shepp's inequality} for the $q$-analogue
of the order polynomial, by using the remarkable \defng{$q$-FKG inequality}
by Bj\"orner.  We continue with the general lower bound on the order
polynomial (Section~\ref{s:OP-inj}), and prove Theorem~\ref{thm:order_le}
by a direct injection.

In Section~\ref{s:restricted}, we prove the vanishing conditions
(Theorem~\ref{t:vanish}) and uniqueness conditions
(Theorem~\ref{t:gen-Stanley-unique}), from which
Corollaries~\ref{cor:Sta-gen-vanish-poly}
and~\ref{cor:Sta-gen-uniqueness-poly} easily follow.
Our proof is based on an algebraic approach of Coxeter group
action on linear extensions,
see~$\S$\ref{ss:finrem-algebraic} for some history of the subject.

In Section~\ref{s:sid}, we give an injective proof of the
Sidorenko inequality, and prove its extension Theorem~\ref{t:sid-gen}.
We then derive Theorem~\ref{t:sid-SP} which is surprisingly
nontrivial given the many other proofs of the inequality
(see~$\S$\ref{ss:finrem-sid}).  We conclude with Section~\ref{s:finrem}
containing lengthy historical remarks and open problems.


\medskip

\section{Basic definitions and notation}  \label{s:notation}
In a poset \hskip.03cm $P=(X,\prec)$, elements \hskip.03cm $x,y\in X$ \hskip.03cm are called
\defn{parallel} or \defn{incomparable} if \hskip.03cm $x\not\prec y$ \hskip.03cm
and \hskip.03cm $y \not \prec x$.  We write \. $x\parallel y$ \. in this case.
Element \hskip.03cm $x\in X$ \hskip.03cm is said to \defn{cover}
\hskip.03cm $y\in X$, if \hskip.03cm $y\prec x$ \hskip.03cm and there are no elements \hskip.03cm $z\in X$ \hskip.03cm
such that \. $y\prec z \prec x$.

A \defn{chain} is a subset \hskip.03cm $C\subset X$ \hskip.03cm of pairwise comparable elements.
The \defn{height} of poset \hskip.03cm $P=(X,\prec)$ \hskip.03cm is the size of the maximal chain.
An \defn{antichain} is a subset \hskip.03cm $A\subset X$ \hskip.03cm of pairwise incomparable elements.
The \defn{width} of poset  \hskip.03cm $P=(X,\prec)$ \hskip.03cm is the size of the maximal antichain.

A \defn{dual poset} \hskip.03cm is a poset \hskip.03cm $P^\ast=(X,\prec^\ast)$, where
\hskip.03cm $x\prec^\ast y$ \hskip.03cm if and only if \hskip.03cm $y \prec x$.

A \defn{disjoint sum} \hskip.03cm $P+Q$ \hskip.03cm of posets \hskip.03cm $P=(X,\prec)$ \hskip.03cm
and \hskip.03cm $Q=(Y,\prec')$ \. is a poset on \hskip.03cm $(X\cup Y,\prec^{\small{\ts\diamond\ts}})$,
where the relation $\prec^{\small{\ts\diamond\ts}}$ coincides with $\prec$ and $\prec'$ on
$X$~and~$Y$, and \. $x\.\|\. y$ \. for all \hskip.03cm $x\in X$, $y\in Y$.

A \defn{linear sum} \hskip.03cm $P\oplus Q$ \hskip.03cm of posets \hskip.03cm $P=(X,\prec)$ \hskip.03cm
and \hskip.03cm $Q=(Y,\prec')$ \. is a poset on \hskip.03cm $(X\cup Y,\prec^{\small{\ts\diamond\ts}})$,
where the relation $\prec^{\small{\ts\diamond\ts}}$ coincides with $\prec$ and $\prec'$ on
$X$~and~$Y$, and \. $x\prec^{\small{\ts\diamond\ts}} y$ \. for all \hskip.03cm $x\in X$, $y\in Y$.

A \defn{product} \hskip.03cm $P\times Q$ \hskip.03cm of posets \hskip.03cm $P=(X,\prec)$ \hskip.03cm
and \hskip.03cm $Q=(Y,\prec^\ast)$ \. is a poset on \hskip.03cm $(X\times Y,\prec^{\small{\ts\diamond\ts}})$,
where the relation \. $(x,y) \preccurlyeq^{\small{\ts\diamond\ts}} (x',y')$  \. if and only if
\. $x \preccurlyeq x'$ \. and \. $y \preccurlyeq^\ast y'$,
for all \hskip.03cm $x,x'\in X$ \hskip.03cm and \hskip.03cm $y,y'\in Y$.

Posets constructed from one-element posets by recursively taking
disjoint and linear sums are called \defn{series-parallel}.
Both \defn{$n$-chain} \hskip.03cm $C_n$ \hskip.03cm and \defn{$n$-antichain} \hskip.03cm $A_n$
 \hskip.03cm are examples of series-parallel posets.

For a subset \hskip.03cm $Y\subset X$, a \hskip.03cm \defn{restriction} \hskip.03cm of the
poset \hskip.03cm $=(X,\prec)$ \hskip.03cm to \hskip.03cm $X\smallsetminus Y$ \hskip.03cm is a subposet
\hskip.03cm $(X\smallsetminus Y,\prec)$ \hskip.03cm of~$P$, which we denote
by \hskip.03cm $P\smallsetminus Y$ \hskip.03cm and \hskip.03cm $P|_{X\smallsetminus Y}$.

For a poset \hskip.03cm $P=(X,\prec)$, a function \hskip.03cm $f: X\to \mathbb R$ \hskip.03cm
is called \defn{$\prec$-increasing} \hskip.03cm if \hskip.03cm $f(x)\le f(y)$ \hskip.03cm
for all \hskip.03cm $x\preccurlyeq y\hskip.03cm;$ such functions are also called
\defn{weakly order-preserving} in a different context.
The \hskip.03cm \defn{$\prec$-decreasing} \hskip.03cm functions
are defined analogously.


Throughout the paper we use \, $\mathbb N=\{0,1,2,\ldots\}$, \.
$\mathbb P=\mathbb N_{\ge 1} =\{1,2,\ldots\}$ \. and \. $[n]=\{1,\ldots,n\}$.


\medskip

\section{Injective proof of the Bj\"orner--Wachs inequality}\label{s:injective}
In this short section we recap the original proof by Bj\"orner and Wachs.  We do
this both as a warmup and as a way to introduce some definitions and ideas
that will prove useful throughout the paper.  As a quick application, we
obtain the proof of Theorem~\ref{t:HP-SP}.  The reader well familiar
with~\cite{BW89} can skip this section.

\smallskip

Denote by \hskip.03cm $\mathcal S=\mathcal S(P)$ \hskip.03cm the set of all bijections
\. $\sigma: X\to [n]$, so that \. $\Ec(P) \subseteq \mathcal S(P)$. Denote by \hskip.03cm $\mathcal B=\mathcal B(P)$ \hskip.03cm
the set of maps \. $g: X\to X$ \. such that \. $g(x)\succcurlyeq x$ \. for all \. $x\in X$.
The inequality~\eqref{eq:HP} can then be written as:
$$(\ast) \qquad
\bigl|\mathcal S(P)\bigr| \, \le \, \bigl|\Ec(P)\bigr| \. \cdot \.  \bigl|\mathcal B(P)\bigr| \..
$$
We prove \hskip.03cm $(\ast)$ \hskip.03cm by a direct injection \. $\Phi: \mathcal S \to \Ec \times \mathcal B$ \.
defined as follows.

We say that a bijection \hskip.03cm $f: X\to [n]$ \hskip.03cm is \defn{sorted} on a subset \hskip.03cm $Y \subseteq X$,
if \. $f(x)< f(y)$ \. for all \. $x, \hskip.03cm y\in Y$ \. such that \. $x\prec y$.
Fix a linear extension \hskip.03cm $\alpha\in \Ec(P)$ and label the elements of $X$ naturally according to $\alpha$, so that $x_i = \alpha^{-1}(i)$.  For every \. $\sigma\in \mathcal S$,
proceed with the following \defng{sorting algorithm} for the elements \.
$x_n,\ldots,x_1$ \. in this order.  At the $k$-th step,
take the element \.
$x=x_{n-k+1}$ \. and let \. $f(x):=\sigma(x)$.
If \hskip.03cm $\sigma(x)$ is the smallest of \hskip.03cm $\{f(y), y\in B(x)\}$, do nothing.
Otherwise, start the \defn{demotion} of \hskip.03cm $x$ \hskip.03cm by  swapping
its value $f(x)$ with the smallest $f(x')$, where \. $x'\in B(x)$.
Repeat this with $x'$, etc., until all elements in \hskip.03cm $B(x)$ \hskip.03cm are sorted.
Let \hskip.03cm $g(x):=y$ \hskip.03cm be the element in $B(x)$ where $x$ is demoted to (i.e. $y$ is the largest element in $B(x)$ affected by the demotion).

At end of the sorting algorithm, we obtain a bijection
\hskip.03cm $f: X\to [n]$ \hskip.03cm that is sorted on the whole~$X$, i.e. $f \in \Ec(P)$.
We also obtain a map \hskip.03cm $g\in \mathcal B(P)$.  Define  \. $\Phi(\sigma):=(f,g)$.

\smallskip


\begin{prop}[{\cite{BW89}}]
\label{p:HP-injection}
The map \. $\Phi: \hskip.03cm \mathcal S(P) \. \to \. \Ec(P)\hskip.03cm\times \hskip.03cm\mathcal B(P)$ \. defined above is an injection.
\end{prop}

\begin{proof}
Define the \emph{inverse construction} as follows. Proceed through the reverse order of the
elements \.
$x_1,\ldots,x_n$.  At \hskip.03cm $(n-k)$-th step,
take the element \. $x=x_{n-k}
\. and let \. $y=g(x)$. At this step, the
bijection \. $f: X\to [n]$ \. is sorted on \. $B(x)$.

Start the \defn{promotion} of $y$ by swapping $f(y)$ with the maximal $f(y')$,
over all \. $x\preccurlyeq y' \prec y$, until eventually $f(y)$ is promoted to
the element~$x$.  Denote by \. $\sigma\in \mathcal S(P)$ \. the result of this iterated promotion and
define a map \. $\Psi(f,g):=\sigma$.

Now observe that for all \. $\sigma\in \mathcal S(P)$ \. we have \. $\Psi(\Phi(\sigma))=\sigma$, since
the map \. $\Psi$ \. retraces each step of $\Phi$ by the properties of promotion and demotion.
This implies that $\Phi$ is an injection and completes the proof of the claim.
\end{proof}

\smallskip


\begin{proof}[Proof of Theorem~\ref{t:HP-SP}]
Let \. $\mathcal H(P)\subseteq \Ec(P) \times \mathcal B(P)$ \. be the set of pairs \.
$(f,g)\in \Ec(P) \times \mathcal B(P)$, such that \. $\Phi(\Psi(f,g))\ne (f,g)$.
By definition, \. $\bigl|\mathcal H(P)\bigr| = \xi(P)$.
Since both $\Phi$ and $\Psi$ are computable in polynomial time, then
so is the membership in~$\mathcal H(P)$.  This proves the result.
\end{proof}

\smallskip

A series-parallel poset \hskip.03cm $P=(X,\prec)$ \hskip.03cm is called an \defn{ordered forest}
if it is a disjoint union of rooted trees, where each tree is rooted it its unique minimal element.

\smallskip

\begin{prop}[{\cite{BW89}}]\label{p:HP-forest}
The Bj\"orner--Wachs inequality~\eqref{eq:HP} is an equality
\hskip.03cm \underline{if and only if} \hskip.03cm $P$ \hskip.03cm is an ordered forest.
\end{prop}


\begin{proof}
As mentioned in the introduction, for the ``if'' direction, the equality
can be easily proved by induction, see e.g.~\cite{Bea,SY}.
For the ``only if'' direction, let \. $x,y,z\in X$ \. be a poset elements such that \.
$x\prec z$, \. $y\prec z$, \. $x \.\|\. y$, and such that
both elements \hskip.03cm $x,y$ \hskip.03cm are covered by~$z$.
We claim that \eqref{eq:HP} is a strict inequality in this case.


In the notation above,
choose \. $g\in \mathcal B(P)$ \. such that \. $g(x)=g(y)=z$ \. and \. $g(s)=s$  \. for all $s \in X \smallsetminus \{x,y\}$.  It is easy
to see that there exists \. $f\in \Ec(P)$, such that \. $f(x)= k-1$, \.
$f(y)=k$ \. and \. $f(z)=k+1$, for some \. $1< k< n$. Assume that $x$ precedes $y$ in the natural labeling.
Applying $\Psi$ we see that after promoting $f(x)$ to $z$, the result is no longer a linear extension on $B(y)$ and thus \. $\Psi \. $ is not defined there. Thus \.$\Phi$\. is not a bijection, which proves the claim.

Finally, observe that $P$ is an ordered forest if and only if every poset
element covers at most one element. This proves the result.
\end{proof}

\medskip

\section{Bounding order polynomial by the FKG inequality} \label{s:OP-induction}


In this section we prove the bound on the order polynomial from
Theorem~\ref{thm:HP order poly} using an inductive approach and an application
of the FKG inequality on the Shepp's lattice.

\smallskip

\subsection{Shepp's lattice and the FKG inequality}\label{ss:Shepp lattice}
Recall that a \defnb{lattice} \. ${\mathcal{L}}:=(L,\prec^{\small{\ts\diamond\ts}})$ \. is a partially ordered set on~$L$,
such that every \hskip.03cm $a,b\in L$ \hskip.03cm has a unique least upper bound called \defnb{join} \hskip.03cm $a \vee b$,
and a unique greatest lower bound called \defnb{meet} \hskip.03cm $a \wedge b$.
A lattice is called \defnb{distributive} \hskip.03cm if
\[ a \wedge (b \vee c) \ = \ (a \wedge b) \vee (a \wedge c) \quad \text{ for all } \ a, \hskip.03cm b, \hskip.03cm c\hskip.03cm \in L\hskip.03cm.
\]
A function \. $\mu: L\to \Rb_{\geq 0}$ \. is called \defnb{log-supermodular} \hskip.03cm
if
\[ \mu(a) \.  \mu(b) \ \leq \  \mu(a \wedge b) \. \mu(a \vee b) \quad \text{ for all } \ a,\hskip.03cm b \in L\hskip.03cm.
\]

Fix a positive integer \hskip.03cm $t>0$.
Let \. $P=(X,\prec)$ \. be a poset on \hskip.03cm $|X|=n$ \hskip.03cm elements, let \. $X=Y \sqcup Z$ \.
be a partition of $X$ into two disjoint subsets.
\defnb{Shepp's lattice} \. ${\mathcal{L}}= {\mathcal{L}}_{Y,Z,t} \ := \ (L,\prec^{\small{\ts\diamond\ts}})$ \. is defined as
	\[
 L \ := \ \big\{ \textbf{\textit{v}} = (v_x)_{x \in X}  \, :  \,  1 \. \leq \. v_x \. \leq \.  t \big\},
 \]
and let
\begin{equation*}
\textbf{\textit{v}} \. \preccurlyeq^{\small{\ts\diamond\ts}} \. \textbf{w}  \quad \Longleftrightarrow
\quad \left\{\aligned  & \, v_y \. \leq \. w_y   & \text{for all} \ \ y \in Y \\
& \, v_z \. \geq \. w_z & \text{for all} \ \ z \in Z \endaligned
\right.
\end{equation*}
Let  \. $\mu=\mu_{Y,Z} \hskip.03cm : \hskip.03cm L \to \{0,1\}$ \. be a function defined as
\begin{equation*}
\mu(\textbf{\textit{v}})=1 \quad \Longleftrightarrow
\quad  v_{x} \ \leq \ v_{x'}  \quad  \text{for all} \ \  x \preccurlyeq x' \ \ \
\text{such that} \ \ \ \left[ \. \aligned & x,x' \in Y\hskip.03cm, \ \, \text{or} \\
& x,x'\in Z\hskip.03cm. \endaligned\right.
\end{equation*}


\smallskip


\begin{thm}[\cite{She}]
	Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset, and let \hskip.03cm $X=Y \sqcup Z$ \hskip.03cm be a partition of
the ground set $X$ into two disjoint subsets. Then
	\. ${\mathcal{L}}_{Y,Z,t}$ \. is a distributive lattice, and \. $\mu_{Y,Z}$ \. is a log-supermodular function.
\end{thm}

\smallskip

This beautiful result is relatively little known;
we include a short proof for completeness.

\smallskip

\begin{proof}
	It follows from the definition of \. $\prec^{\small{\ts\diamond\ts}}$\hskip.03cm,  that for all \. $\textbf{\textit{v}}, \textbf{w} \in L$, we have:
	 \begin{equation}\label{eq:She1}
	 \begin{split}
	 	& (\textbf{\textit{v}} \wedge \textbf{w})_{y} \ = \  \min\{v_y, w_y\}, \qquad  (\textbf{\textit{v}} \wedge \textbf{w})_{z} \ = \  \max\{v_z, w_z\},\\
	 	& (\textbf{\textit{v}} \vee \textbf{w})_{y} \ = \  \max\{v_y, w_y\}, \qquad  (\textbf{\textit{v}} \vee \textbf{w})_{z} \ = \  \min\{v_z, w_z\},
	 \end{split}
	 \end{equation}
 where \hskip.03cm $y \in Y$ \hskip.03cm and \hskip.03cm $z \in Z$.
 Now note that, for all real numbers \. $\alpha,\beta, \gamma \in \Rb$\.,
 \begin{equation}\label{eq:She2}
 	\min\{\alpha, \max\{\beta,\gamma\} \} \ = \ \max \{ \min \{\alpha,\beta\}, \. \min \{\alpha,\gamma\} \}.
 \end{equation}
It then follows from \eqref{eq:She1} and \eqref{eq:She2} that \hskip.03cm ${\mathcal{L}}$ \hskip.03cm is a distributive lattice.

To show that $\mu$ is a log-supermodular function,
it suffices to verify the cases when \. $\mu(\textbf{\textit{v}})= \mu(\textbf{w})=1$\hskip.03cm.
Let \. $y,y' \in Y$ \. be such that $y \prec y'$.
Note that \. $v_y \leq v_{y'}$ \. and \. $w_y \leq w_{y'}$.
Then we have:
\[
(\textbf{\textit{v}} \wedge \textbf{w})_y \ = \ \min\{v_y, w_y\}  \ \leq \  \min\{v_{y'}, w_{y'}\} \ = \  (\textbf{\textit{v}} \wedge \textbf{w})_{y'}\..
\]
Similarly, we have \. $(\textbf{\textit{v}} \wedge \textbf{w})_{z} \. \leq \. (\textbf{\textit{v}} \wedge \textbf{w})_{z}$ \. for all  \. $z \prec z'$, \. $z, z' \in Z$.
Therefore, \. $\mu(\textbf{\textit{v}} \wedge \textbf{w})=1$.
Analogously, we also have \. $\mu(\textbf{\textit{v}} \vee \textbf{w})=1$\., and the proof is complete.
\end{proof}

\smallskip

\begin{rem}
Shepp's lattice \hskip.03cm ${\mathcal{L}}$ \hskip.03cm used in this section should not be confused with another lattice
defined in~\cite{She-XYZ} by Shepp.  Both lattices share the same ground set but have different
partial orders, and the partial order of the lattice in \cite{She-XYZ} was specifically chosen
to prove the \defng{$XYZ$ \hskip.03cm inequality}.
\end{rem}

\smallskip

Now recall the classical \defn{FKG inequality}, see e.g.~\cite[$\S$6.2]{ASE}.

\smallskip

\begin{thm}[{\rm {\em{\defn{FKG inequality}}}, \cite{FKG}}]\label{thm:FKG}
	Let \. ${\mathcal{L}}=(L,\prec)$ \. be a finite distributive lattice, and let
\. $\mu: L \to \Rb_{\geq 0}$ \. be a log-supermodular function.
Then, for every \hskip.03cm $\prec^{\small{\ts\diamond\ts}}$-decreasing functions \.
$g,h: \hskip.03cm L \to \Rb_{\geq 0}$\hskip.03cm, we have:
\begin{equation}\label{eq:FKG-ineq}
E(\textbf{\em 1}) \. E(gh) \ \geq  \  E(g) \. E(h),
\end{equation}
	where \.
	\[ E(g) \, = \, E_\mu(g) \ := \  \sum_{a \in L} \, g(x) \. \mu(x)\., \]
and function \. $\textbf{\em 1}:L \to \Rb$ \. is given by \. $\textbf{\em 1}(a)=1$ \. for all \hskip.03cm $a \in L$.

The inequality~\eqref{eq:FKG-ineq} holds also when \hskip.03cm $g,h$ \hskip.03cm are $\prec^{\small{\ts\diamond\ts}}$-increasing.
On the other hand, for \hskip.03cm $g$ is $\prec^{\small{\ts\diamond\ts}}$-decreasing and $h$ is $\prec^{\small{\ts\diamond\ts}}$-increasing,
 the inequality~\eqref{eq:FKG-ineq} is reversed.
\end{thm}

\smallskip

Below we apply the FKG inequality to Shepp's lattice to prove several
inequalities for the order polynomial.

\medskip

\subsection{Correlation inequalities} \label{ss:OP-induction-prelim}
Let \. $P=(X,\prec)$ \. be a poset on $n$ elements.  As above, denote by \hskip.03cm $\mathcal S=\mathcal S(P)$ \hskip.03cm the
set of bijections \hskip.03cm $f: X\to [n]$.
By an abuse of notation, for every (not necessarily distinct) elements \. $u,  v\in X$,
we write
\[
\{\hskip.03cm u \precc v  \hskip.03cm \}  \qquad \text{as a shorthand for the collection} \qquad
\{\hskip.03cm f \in \mathcal S \. : \. f(u) \le  f(v) \hskip.03cm \}\..
\]
One can write the set of linear extensions \hskip.03cm $\Ec(P)$ \hskip.03cm as the intersection of
collections \. $\{u\precc v\}$, for all pairs \hskip.03cm $u\prec v$ \hskip.03cm in~$P$.  Conversely,
every such intersection is a set of linear extensions of the corresponding poset.
The language of \defn{collections} is technically useful for our purposes.

Let \. $X= Y \. \sqcup \. Z$ \. be a \defn{partition} of~$X$ into two disjoint subsets.
A collection \hskip.03cm $C$ \hskip.03cm is called \hskip.03cm \defn{$Y$-minimizing} \hskip.03cm w.r.t.\
the partition \hskip.03cm $Y\sqcup Z$ \hskip.03cm
if $C$ is an intersection of collections of the form \. $\{y\precc z\}$,
for \. $y\in Y$ \. and \. $z\in Z$.
Similarly,
a collection \hskip.03cm $C$ \hskip.03cm is called \defn{$Y$-maximizing} w.r.t.\  the partition \hskip.03cm $Y\sqcup Z$ \hskip.03cm
if $C$ is an intersection of collections of the form \. $\{z\precc y\}$,
for \. $y\in Y$ \. and \. $z\in Z$.
By a slight abuse of notation, we write \hskip.03cm $\Omega(C,t)$ \hskip.03cm
to denote the order polynomial of a poset given by the collection~$C$.

For the rest of this section, let \hskip.03cm $A$ \hskip.03cm be the collection given by
\begin{equation*}\label{eq:colA}
	A \ := \  \bigcap_{y\prec y', \ y, y'\in Y} \. \{ y \precc y' \}\hskip.03cm \ \cap \ \bigcap_{z\prec z', \ z, z'\in Z} \. \{ z \precc z' \}\hskip.03cm,
\end{equation*}
the collection of events involving only elements of $Y$ or only elements of $Z$.
\smallskip

\begin{lemma}[{\cite[Eq.~(2.12)]{She}}]\label{t:FKG order polynomial}

In the notation above,  let \hskip.03cm $C,C'$ \hskip.03cm
be $Y$-minimizing collections w.r.t.\ partition \ $X=Y\sqcup Z$. Then, for every integer \hskip.03cm $t>0$, we have:
\[
\Omega \big(C  \cap   C' \cap A,\hskip.03cm t\big)  \. \cdot \.  \Omega\big( A,\hskip.03cm t\big)
\quad \geq \quad \Omega \big(C \cap A,\hskip.03cm t\big)  \. \cdot \.  \Omega\big( C' \cap A,\hskip.03cm t\big)\..	
\]
If $C$ is $Y$-minimizing and $C'$ is $Y$-maximizing, then the above inequality is reversed.
\end{lemma}

\smallskip

In the probabilistic language, it says that the order polynomial
satisfies \defna{positive correlation} for intersections of $Y$-minimizing
collections (viewed as events).  We should note that in~\cite{She} this
result was not singled out and appears as an equation in the middle of
the proof of the main result.  We again include the proof for completeness.

\smallskip

\begin{proof}[Proof of Lemma~\ref{t:FKG order polynomial}]
Let \hskip.03cm ${\mathcal{L}}=(L,\prec^{\small{\ts\diamond\ts}})$ \hskip.03cm be Shepp's lattice defined in~$\S$\ref{ss:Shepp lattice}.
Let \. $g,h : L \to \{0,1\}$ \. be given by
	\[  g(\textbf{\textit{v}})  \ := \
\begin{cases}
	\. 1 & \text{if} \ \  v_y  \hskip.03cm \leq \hskip.03cm v_z \ \ \, \forall \. \{ y \precc z\} \in C\\
	\. 0 & \text{otherwise}
\end{cases} \quad \text{and}
\quad  h(\textbf{\textit{v}})  \ := \
\begin{cases}
	\. 1 & \text{if} \ \  v_y  \hskip.03cm \leq \hskip.03cm v_z  \ \ \, \forall \. \{ y \precc z\} \in C'\\
	\. 0 & \text{otherwise.}
\end{cases}
\]
Let us prove that \hskip.03cm $g$ \hskip.03cm is $\prec^{\small{\ts\diamond\ts}}$-decreasing.
It suffices to show that
\begin{equation*
g(\textbf{w})\hskip.03cm =\hskip.03cm 1 \quad \text{and} \quad \textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w} \quad \Longrightarrow \quad  g(\textbf{\textit{v}})\hskip.03cm = \hskip.03cm 1.
\end{equation*}
Note that for every \hskip.03cm $y \in Y$ \hskip.03cm and \hskip.03cm $z \in Z$ \hskip.03cm such that \hskip.03cm $y \preccurlyeq z$, we have:
 \[  v_y \ \leq \  w_y \ \leq \ w_z \ \leq \ v_z, \]
where the first and the third inequality is because \hskip.03cm $\textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w}$\hskip.03cm, and the second inequality is because $g(\textbf{w})=1$.
This implies that $g(\textbf{\textit{v}})=1$, and thus $g$ is a $\prec^{\small{\ts\diamond\ts}}$-decreasing function.
By the same reasoning, we also have that function \hskip.03cm $h$ \hskip.03cm is $\prec^{\small{\ts\diamond\ts}}$-decreasing.

Finally, note that
\begin{align*}
	\Omega(C \cap C' \cap A, t) \. = \. E(gh), \ \  \Omega( A, t) \. = \. E(\textbf{1}),
	\ \  \Omega(C  \cap A, t) \. = \. E(g),
	\ \  \Omega(C' \cap A, t) \. = \. E(h),
\end{align*}
The lemma now follows from the FKG inequality (Theorem~\ref{thm:FKG}).
\end{proof}

\smallskip

We can now apply this result in the more traditional notation of order polynomials
of posets.

\smallskip

\begin{lemma}\label{l:main order polynomial}
	Let \. $P=(X,\prec)$ \. be a poset, and let \. $x,y\in X$ \. be minimal elements.
	Then, for every integer $t>0$, we have:
\[ {\Omega\big(P,\hskip.03cm t\big)} \. \cdot \. {\Omega\big(P \smallsetminus \{x,y\},\hskip.03cm t\big)}  \ \geq \  {\Omega\big(P \smallsetminus x, \hskip.03cm t\big)}  \. \cdot \.  {\Omega\big(P\smallsetminus y,\hskip.03cm t\big)},
\]
where by \hskip.03cm $P\smallsetminus x$, \hskip.03cm $P\smallsetminus y$ \hskip.03cm and \hskip.03cm $P\smallsetminus \{x,y\}$ \hskip.03cm denote the
subposets of~$\hskip.03cm P$ \hskip.03cm restricted to \hskip.03cm $X-x$, \hskip.03cm \hskip.03cm $X-y$ \hskip.03cm and \hskip.03cm $X-x-y$, respectively.
\end{lemma}

\smallskip

\begin{proof}
Note that \. $x$ \hskip.03cm and \hskip.03cm $y$ \. are incomparable elements.
Let \. $Y:= \{x,y \}$ \. and \. $Z:= X\smallsetminus Y$ \. be the partition of~$X$.
Consider the $Y$-minimizing collections \. $C$ \hskip.03cm and \hskip.03cm $C'$ \. given by
\begin{equation}\label{eq:colC}
C  \ := \ \bigcap_{z\in B(x)-x} \. \{ x \precc z \} \ \, \quad \text{and} \quad \  C'  \ := \  \bigcap_{z'\in B(y)-y} \. \{ y \precc z' \},
\end{equation}
where \hskip.03cm $B(x)$ \hskip.03cm and \hskip.03cm $B(y)$ \hskip.03cm are upper order ideals of elements~$x$ and~$y$, respectively.
Observe that
	\begin{alignat*}{2}
	 & \Omega(P,t) \ = \  \Omega(C \cap C' \cap A,t)\., \qquad  && \Omega(P\smallsetminus x,t) \ = \  \frac{1}{t} \,\. \Omega(C' \cap A,t)\.,\\
	    	& \Omega(P \smallsetminus y,t) \ = \  \frac{1}{t} \, \Omega(C \cap A,t)\., \qquad  && \Omega(P \smallsetminus \{x,y\},t) \ = \  \frac{1}{t^2} \, \Omega(A,t)\..
	\end{alignat*}
	The lemma now follows from  Lemma~\ref{t:FKG order polynomial}
	and the equations above.
\end{proof}

\smallskip

\subsection{Lower bounds}\label{ss:OP-induction-lower}
We are now ready to prove Theorem~\ref{thm:HP order poly} by induction.
The following lemma established the induction step from which the
theorem follows.

\smallskip

\begin{lemma}\label{l:OP-HP-ind}
Let \. $P=(X,\prec)$ \. be a poset with \. $|X|=n$ \. elements, and let \hskip.03cm $x\in X$ \hskip.03cm
be a minimal element such that \hskip.03cm $b(x)>1$.
Then we have:
\begin{equation}\label{eq:HP-ind-min}
\frac{\Omega(P,t)}{t+1} \ \geq \ \frac{\Omega(P\smallsetminus x,t)}{b(x)}\..
\end{equation}
\end{lemma}

\begin{proof}  Let \hskip.03cm $Q=(Y,\prec)$ \hskip.03cm be a finite poset.
By labeling the elements in~$Y$ with $m$ distinct integers from~$\hskip.03cm [t]$,
we can write
\begin{align}\label{eq:sum_ideals}
\Omega(Q,t) \ = \ \sum_{m=1}^n \, \bigl|\mathcal I_m(Q)\bigr| \, \binom{t}{m}\.,
\end{align}
where \. $|\mathcal I_m(Q)|$ \. is the number of ascending chains
$$\varnothing \. = \. I_0 \. \subset \. I_1 \. \subset \. I_2 \. \subset \. \ldots \. \subset \. I_m \. = \.Q
$$
\. of  upper order ideals in~$P$, s.t.\ \. $I_i \smallsetminus I_{i-1} \neq \varnothing$ \. for all \hskip.03cm $1\le i \le m$.

Denote by \. $P' = P \smallsetminus \{x\}$ \. the induced poset on \hskip.03cm $X \smallsetminus x$.
Suppose that $x$ is a unique minimal element of $P$, and let \. $P'=P\smallsetminus x$.
Note that \. $b(x)=n$ \. in this case.
Summing over all possible values of~$x$, we obtain~\eqref{eq:HP-ind-min}:
\begin{align*}
\Omega(P,t) \ &=  \ \sum_{k=1}^t \. \Omega(P',k) \ =_{\eqref{eq:sum_ideals}} \
\sum_{m=1}^{n-1} \, \bigl|\mathcal I_m(P')\bigr| \, \sum_{k=m}^t \. \binom{k}{m} \ = \ \sum_{m=1}^{n-1} \, \bigl|\mathcal I_m(P')\bigr| \,  \binom{t+1}{m+1} \\
& \geq \ \frac{t+1}{n} \, \sum_{m=1}^{n-1} \, \bigl|\mathcal I_m(P')\bigr| \,   \binom{t}{m} \ =_{\eqref{eq:sum_ideals}} \ \frac{t+1}{n} \ \Omega(P',t)\..
\end{align*}
Here the inequality follows from
$$\binom{t+1}{m+1} \ = \ \frac{t+1}{m+1} \. \binom{t}{m} \ \geq \ \frac{t+1}{n} \. \binom{t}{m} \quad \ \.\text{for all \ $m\leq n-1$.}
$$


Suppose now that \hskip.03cm $x\in X$ \hskip.03cm is not a unique minimal element.  Let \hskip.03cm $y\in X$, \hskip.03cm $y\ne x$ \hskip.03cm
be another minimal element in~$P$.  By Lemma~\ref{l:main order polynomial}, we have:
\begin{equation}\label{eq:FKG2}
\frac{\Omega(P,t)}{\Omega(P',t)} \ \geq \ \frac{\Omega(P \smallsetminus y, t)}{\Omega(P' \smallsetminus y, t)} \,.
\end{equation}
Now proceed by induction to remove all minimal elements in~$P$ incomparable to~$x$,
until element~$x$ becomes
the unique minimal element.
Applying the inequality~\eqref{eq:FKG2} repeatedly, we obtain:
\begin{equation*
\frac{\Omega(P,t)}{\Omega(P',t)} \ \geq \
\ldots \ \geq \ \frac{t+1}{b(x)}\,.
\end{equation*}
This proves~\eqref{eq:HP-ind-min} in full generality.
\end{proof}

\smallskip

\begin{proof}[Proof of Theorem~\ref{thm:HP order poly}]
We prove the inequality~\eqref{eq:OP-HP} by induction.
First, suppose that \hskip.03cm $b(x)=1$, so \hskip.03cm $x$ \hskip.03cm is the maximal element in~$P$.
Then \. $\Omega(P,t) \hskip.03cm = \hskip.03cm t \. \Omega(P',t)$, since we can choose the value \hskip.03cm
$f(x)\in [t]$ \hskip.03cm independently of other values.  The inequality~\eqref{eq:OP-HP}
follows then.  For \. $b(x)>1$,  Lemma~\ref{l:OP-HP-ind} gives the step of
induction and complete the proof.
\end{proof}

\medskip

\subsection{Log-concavity}\label{ss:OP-log-concavity}
The main result of this subsection is the log-concavity of the evaluation of the order polynomial.


\smallskip

\begin{thm}\label{thm:log-concave}
	Let $P=(X,\prec)$ be a finite poset.
	Then, for every integer \hskip.03cm $t \geq 2$, we have:
	\[ \Omega(P,t)^2  \  \geq \ \Omega(P,t+1) \. \cdot\.  \Omega(P,t-1).\]
\end{thm}

\smallskip

As for other poset inequalities, one can ask about equality conditions of
in Theorem~\ref{thm:log-concave}.  Turns out, the log-concavity in the theorem
is always strict, see Theorem~\ref{thm:log-concave-strict} below.
The proof of both results use the same approach, but the strict
log-concavity is built on top of the non-strict version and is
a bit more involved.  Thus, we start with the easier result for clarity.

\smallskip

\begin{proof}[Proof of Theorem~\ref{thm:log-concave}]
Let \hskip.03cm $Y=X$ \hskip.03cm and \hskip.03cm $Z=\varnothing$.
Let \hskip.03cm ${\mathcal{L}}=(L,\prec^{\small{\ts\diamond\ts}})$ \hskip.03cm be Shepp's lattice defined in~$\S$\ref{ss:Shepp lattice}, and let \hskip.03cm $t\geq 3$.
		 Let \. $g,h : L \to \{0,1\}$ \. be two functions given by
				\begin{align*}
			g(\textbf{\textit{v}}) \ &:= \
			\begin{cases}
				\. 1 & \text{if} \ \ v_x \geq 2 \ \ \text{ for all \ $x \in X$}\\
				\. 0 & \text{otherwise},
			\end{cases} \quad
			h(\textbf{\textit{v}}) \ := \
			\begin{cases}
				\. 1 & \text{if} \ \ v_x \leq t-1 \ \ \text{ for all \ $x \in X$}\\
				\. 0 & \text{otherwise}.  	
			\end{cases}
		\end{align*}
To prove that $g$ is $\prec^{\small{\ts\diamond\ts}}$-increasing, it suffices to show that
\begin{equation*
g(\textbf{\textit{v}})\hskip.03cm =\hskip.03cm 1 \quad \text{and} \quad \textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w} \quad \Longrightarrow \quad  g(\textbf{w})\hskip.03cm = \hskip.03cm 1.
\end{equation*}
Note that, for every \hskip.03cm $x \in Y=X$, we have:
\[
w_x \, \geq \,  v_x \, \geq \, 2,
\]
where the first  inequality is because \hskip.03cm $\textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w}$\hskip.03cm, and the second inequality is because $g(\textbf{\textit{v}})=1$.
This implies that $g(\textbf{w})=1$, and thus $g$ is a $\prec^{\small{\ts\diamond\ts}}$-increasing function.
By an analogous reasoning we also have that $h$ is $\prec^{\small{\ts\diamond\ts}}$-decreasing.	
	
		Now note that
		\begin{equation}\label{eq:expectation-as-OP}
		\begin{split}
			E(gh) \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,  2 \. \leq \. v_x \. \leq \. t-1  \, \ \text{ for all } \,\  x \in X\big\} \big| \ = \  \Omega(P,t-2),\\
			E(g)  \ &= \   \big|\big\{ \textbf{\textit{v}} \in L \. : \,  2 \. \leq \. v_x \, \ \text{ for all } \, \ x \in X\big\} \big| \ = \   \Omega(P,t-1),\\
			E(h) \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,  v_x \. \leq \. t-1  \,\ \text{ for all } \, \ x \in X\big\} \big| \ = \  \Omega(P,t-1),\\
			E(\textbf{1})  \ &= \  |L| \ = \ \Omega(P,t).
		\end{split}
		\end{equation}
		It then follows from the FKG inequality~(Theorem~\ref{thm:FKG}), that
		\[ \Omega(P,t-2) \.\cdot\. \Omega(P,t) \ \leq  \ \Omega(P,t-1) \.\cdot\. \Omega(P,t-1), \]
		and the theorem now follows by substituting \. $t\to t+1$.
\end{proof}

\medskip


\subsection{Strict log-concavity}
We can now prove that the inequality in Theorem~\ref{thm:log-concave} is always strict,
by applying the FKG inequality in a more careful manner.  This theorem will also
proved useful in~$\S$\ref{ss:OP-Graham} to establish the asymptotic version of
Graham's Conjecture~\ref{conj:Graham}.

\smallskip

\begin{thm}\label{thm:log-concave-strict}
	Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.
	Then, for every integer \hskip.03cm $t \geq 2$, we have:
	\begin{equation}\label{eq:log-concave-strict}
	 \Omega(P,t)^2  \  \geq \ \bigg(1 \. + \. \frac{1}{(t+1)^{n+1}} \bigg) \    \Omega(P,t+1) \   \Omega(P,t-1).
	\end{equation}
\end{thm}

	
\smallskip


Let \hskip.03cm $Y=X$ \hskip.03cm and \hskip.03cm $Z=\varnothing$.
Let \hskip.03cm ${\mathcal{L}}=(L,\prec^{\small{\ts\diamond\ts}})$ \hskip.03cm be Shepp's lattice, let \hskip.03cm $\mu = \mu_{Y,Z} \hskip.03cm : \hskip.03cm L \to \{0,1\}$ \hskip.03cm
be the log-supermodular function defined in~$\S$\ref{ss:Shepp lattice}, and let \hskip.03cm $t\geq 3$.
Without loss of generality, assume that \hskip.03cm $X=[n]$ \hskip.03cm and that this is a \defn{natural labeling}
of~$X$, i.e.\  \. $i<j$ \. for all \. $i \prec j$.
	
	For all \hskip.03cm $1\le i\le n$,
	let \. $g_i,h_i : L \to \{0,1\}$ \. be two functions given by
	\begin{align*}
		g_i(\textbf{\textit{v}}) \ &:= \
		\begin{cases}
			\. 1 & \text{if} \ \ v_i \geq 2 \\
			\. 0 & \text{otherwise}
		\end{cases} \qquad \text{and} \qquad
		h_i(\textbf{\textit{v}}) \ := \
		\begin{cases}
			\. 1 & \text{if} \ \ v_i \leq t-1 \\
			\. 0 & \text{otherwise}.	
		\end{cases}
	\end{align*}
In notation of the proof of Theorem~\ref{thm:log-concave},
we have \. $g=g_1\cdots g_n$ \. and  \. $h=h_1\cdots h_n$.

It follows from the same argument above, that \hskip.03cm $g_i$ \hskip.03cm are $\prec^{\small{\ts\diamond\ts}}$-increasing,
while \hskip.03cm $h_i$ \hskip.03cm are $\prec^{\small{\ts\diamond\ts}}$-increasing, for all \hskip.03cm $1\le i\le n$.
We now show that $g_i$ and $h_i$ are log-modular functions.
Indeed, note that
\[   v_i \geq 2 \ \text{ and } \ w_i \geq 2 \qquad \Longleftrightarrow \qquad \max\{v_i, w_i \} \geq 2  \ \text{ and } \ \min\{v_i, w_i \} \geq 2.  \]
This implies that 	\. $g_i(\textbf{\textit{v}}) \. g_i(\textbf{w}) \ = \ g_i(\textbf{\textit{v}} \wedge \textbf{w}) \.
g_i(\textbf{\textit{v}} \vee \textbf{w})$, as desired.
The same argument implies that $h_i$ is also a log-modular function.

\smallskip

\begin{lemma}
	\begin{equation}\label{eq:remove-g}
		 \frac{E_\mu(g_1\hskip.03cm \cdots \hskip.03cm g_n \cdot h)}{E_\mu(g_1\hskip.03cm\cdots \hskip.03cm g_n)}  \ \leq \
	\frac{E_\mu(g_n \hskip.03cm h )}{E_\mu(g_n)}.
	\end{equation}
\end{lemma}

\begin{proof}
Let \hskip.03cm $\mu_i: L \to \Rb$ \hskip.03cm be given by \. $\mu_i :=  (g_i  \hskip.03cm \cdots \hskip.03cm g_n) \hskip.03cm \mu$,
for all \. $1\le i \le n$, and let \hskip.03cm $\mu_{n+1}:=\mu$.
Note that function \hskip.03cm $\mu_i$ \hskip.03cm is a log-supermodular since it is a product of
log-modular and log-supermodular functions.
Therefore, for all \hskip.03cm $2\le i \le n$, we have:
	\begin{equation}\label{eq:remove-g-induction}
		 \frac{E_{\mu_{i}}(g_{i-1} \hskip.03cm h)}{E_{\mu_{i}}(g_{i-1} \hskip.03cm )} \ \leq \ \frac{E_{\mu_{i}}( h)}{E_{\mu_{i}}(\textbf{1})} \ = \ \frac{E_{\mu_{i+1}}(g_i \hskip.03cm h)}{E_{\mu_{i+1}}(g_i)}\,,
	\end{equation}
where the inequality is by  the FKG inequality (Theorem~\ref{thm:FKG}) applied to the  $\prec^{\small{\ts\diamond\ts}}$-increasing function~$g_{i-1}\hskip.03cm$,
to the $\prec^{\small{\ts\diamond\ts}}$-decreasing function~$\hskip.03cm h$, and to the log-supermodular function~$\hskip.03cm\mu_i\hskip.03cm$.
We conclude:
\[ 		 \frac{E_\mu(g_1\hskip.03cm\cdots\hskip.03cm g_n \cdot h)}{E_\mu(g_1\hskip.03cm\cdots\hskip.03cm g_n)}  \ = \  \frac{E_{\mu_2}(g_1 \hskip.03cm h)}{E_{\mu_2}(g_1 )}   \leq \
\frac{E_{\mu_{n+1}}(g_n \hskip.03cm h )}{E_{\mu_{n+1}}(g_n)}  \ = \ \frac{E_{\mu}(g_n \hskip.03cm h )}{E_{\mu}(g_n)}\,,  \]
where the inequality is by consecutive applications of \eqref{eq:remove-g-induction}.
\end{proof}

\smallskip

Now, let \. $\eta_i:= (h_i\hskip.03cm \cdots \hskip.03cm h_n) \hskip.03cm  \mu$ \. for all \. $1\le i\le n$, and let \. $\eta_{n+1}:=\mu$.
	Again, note that \hskip.03cm $\eta_i$ \hskip.03cm is a log-supermodular function.
	Observe  that \. $E_{\eta_i}[g_n] \. = \. E_{\eta_{i+1}}[g_n \hskip.03cm h_i]$ \. for all \. $2\le i \le n$.
	This implies that
\begin{equation}\label{eq:remove-h}
	\frac{E_{\mu}(g_n \hskip.03cm h )}{E_{\mu}(g_n)} \ = \  \prod_{i=2}^{n+1} \. \frac{E_{\eta_i}(g_n \hskip.03cm h_{i-1})}{E_{\eta_i}(g_n)}\..
\end{equation}	


We apply two different inequalities to the RHS of~\eqref{eq:remove-h}.
First, for all \hskip.03cm $2\le i\le n$, we have:
\begin{equation}\label{eq:easy-FKG}
	\frac{E_{\eta_i}(g_n \hskip.03cm h_{i-1})}{E_{\eta_i}(g_n)} \ \leq \ \frac{E_{\eta_i}(h_{i-1})}{E_{\eta_i}(\textbf{1})} \ = \   \frac{E_{\mu}(h_{i-1} h_i\ldots h_n)}{E_{\mu}(h_{i} \ldots h_n)}\,,
\end{equation}
where the inequality is due to the FKG inequality~(Theorem~\ref{thm:FKG}) applied to the  $\prec^{\small{\ts\diamond\ts}}$-increasing function~$\hskip.03cm g_n$,
to the $\prec^{\small{\ts\diamond\ts}}$-decreasing function~$\hskip.03cm h_{i-1}\hskip.03cm$, and to the log-supermodular
function~$\hskip.03cm\eta_i$.
Although \eqref{eq:easy-FKG} holds for \hskip.03cm $i=n+1$ \hskip.03cm by the same argument,
we will use the following stronger inequality instead.

\smallskip

\begin{lemma}\label{lem:strict-FKG}
	\begin{equation}\label{eq:strict-FKG}
	 \frac{E_{\eta_{n+1}}(g_n \hskip.03cm h_{n})}{E_{\eta_{n+1}}(g_n)}  \ \leq \ \bigg(1-\frac{1}{t^{n+1}} \bigg) \frac{E_\mu(h_n)}{E_{\mu}(\textbf{\em 1})}.
	\end{equation}
\end{lemma}


\begin{proof
	By a direct calculation, the claim  is equivalent to showing that
	\[     \frac{E_{\mu}(g_n) \. E_{\mu}(h_n) \, - \, E_\mu(g_n h_n) \. E_{\mu}(\textbf{1})}{E_{\mu}(g_n) \. E_{\mu}(h_n)} \ \geq \ \frac{1}{t^{n+1}}\.. \]
	Let \. $g_n',h_n':L \to \{0,1\}$ \. be given by \. $g_n'(\textbf{\textit{v}}) :=  1- g_n(\textbf{\textit{v}})$ \. and \. $h_n'(\textbf{\textit{v}}) := 1- h_n(\textbf{\textit{v}})$.
Then we have:
	\begin{align*}
			 g_n'(\textbf{\textit{v}}) \, = \,
		\begin{cases}
			1 & \text{ if } \ v_n \. = \. 1\\
			0 & \text{ otherwise}
		\end{cases} \qquad \text{and}	\qquad		
h_n'(\textbf{\textit{v}})  \, = \,
	\begin{cases}
	1 & \text{ if } \ v_n \. = \. t\\
	0 & \text{ otherwise.}
\end{cases} 	\end{align*}
By the linearity of expectations, the claim is then equivalent to showing that
\begin{equation}\label{eq:strict-correlation}
   \frac{E_{\mu}(g_n') \. E_{\mu}(h_n') \ - \ E_\mu(g_n' h_n') \. E_{\mu}(\textbf{1})}{E_{\mu}(g_n) \. E_{\mu}(h_n)} \ \geq \ \frac{1}{t^{n+1}}.
\end{equation}
Now note that, since $n$ is a maximal element of $P$, we have:
\begin{align*}
	E_\mu(g_n') \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,   v_n \. = \. 1\big\}  \big| \ \geq \, 1,\\
	E_\mu(h_n') \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,   v_n \. = \. t\big\}  \big| \ = \,  \Omega(P\smallsetminus\{n\},t),\\
	E_{\mu}(g_n'h_n') \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,   v_n \. = \. 1 \. = \. t\big\}  \big| \ = \, 0,\\
	E_{\mu}(g_n)   \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,   v_n \. \geq  \. 2 \big\}  \big|  \  \leq \, t \. \Omega(P\smallsetminus\{n\},t),\\
	E_{\mu}(h_n)   \ &= \  \big|\big\{ \textbf{\textit{v}} \in L \, : \,   v_n \. \leq  \. t-1 \big\}  \big|  \  \leq \,  \Omega(P,t) \, \leq \, t^n.
\end{align*}
The inequalities above directly imply \eqref{eq:strict-correlation}.
\end{proof}


\smallskip

\begin{proof}[Proof of Theorem~\ref{thm:log-concave-strict}]
Combining \eqref{eq:remove-g}, \eqref{eq:remove-h}, \eqref{eq:easy-FKG}, and \eqref{eq:strict-FKG},
we get:
\[  \frac{E_{\mu}(gh)}{E_{\mu}(g)}  \ \leq \  \bigg(1\.- \.\frac{1}{t^{n+1}} \bigg) \. \frac{E_\mu(h)}{E_\mu(\textbf{1})}\..\]
Using the values from \eqref{eq:expectation-as-OP}, we obtain:
\[  \frac{\Omega(P,t-2)}{\Omega(P,t-1)} \ \leq \  \bigg(1\.- \. \frac{1}{t^{n+1}} \bigg) \. \frac{\Omega(P,t-1)}{\Omega(P,t)}\..\]
The theorem now follows by substituting \. $t\gets t+1$.
\end{proof}

\smallskip

\begin{rem}
The term \. $\big(1+1/t^{n+1}\big)$ \. in~\eqref{eq:strict-FKG} is far from optimal
and can be improved in many cases.  In particular, note that in the proof of
Lemma~\ref{lem:strict-FKG} we used a separate calculation for an element~$n$
in \hskip.03cm $X=[n]$.  Making this calculation for a general element \hskip.03cm $x \in [n]$,
gives a lower bound with the term \. $\big(1+C/t^{\ell(x)+b(x)}\big)$, for some \hskip.03cm
$C>0$. Thus \hskip.03cm $x=n$ \hskip.03cm  is the \emph{least optimal choice} for the lower bound,
and is made for clarity. \end{rem}


\medskip

\subsection{Kahn--Saks conjecture}\label{ss:OP-KS-mono}

The following interesting conjecture can be found in the solution to
Exc.~3.163(b) in~\cite{Sta-EC}.

\smallskip

\begin{conj}[{\rm \defn{\em Kahn--Saks monotonicity conjecture}}{}]\label{conj:KS-mon}
For a poset \hskip.03cm $P=(X,\prec)$ \hskip.03cm with \hskip.03cm $|X|=n$ \hskip.03cm elements,
the \hskip.03cm \defn{scaled order polynomial} \. $\Omega(P,t)/t^n$ \. is weakly decreasing
on~$\hskip.03cm\mathbb N_{\ge 1}$.
\end{conj}

\smallskip

As Stanley points out in~\cite[Exc.~3.163(a)]{Sta-EC}, the conjecture
holds for \hskip.03cm $t$ \hskip.03cm large enough, since the coefficient \hskip.03cm $[t^{n-1}] \hskip.03cm\Omega(P,t)>0$.
Curiously, the proof is based on an elegant direct injection.
Now, to fully appreciate the power of this conjecture, let us derive from it the following
unusual extension of Theorem~\ref{thm:HP order poly}.


\smallskip
\begin{thm} \label{t:OP-via-KS-mon}
	Let \. $P=(X,\prec)$, let \. $\max(P)\subseteq X$ \. be the subset of maximal elements,
	and let \. $r:=|\max(P)|$ \. be the number of maximal elements. If Conjecture~\ref{conj:KS-mon}
	holds, then we have:
	\begin{equation}\label{eq:OP-analytic}
		\Omega(P,t) \ \geq \
		t^r \prod_{x \hskip.03cm\in\hskip.03cm X\smallsetminus \max(P)} \. \bigg(\frac{t}{b(x)}\,+\,\frac{1}{2}\bigg).
	\end{equation}
\end{thm}

\smallskip

Compared to~\eqref{eq:OP-HP}, the inequality \eqref{eq:OP-analytic}
adds \hskip.03cm $\tfrac12$ \hskip.03cm to every term in the product.
It would be interesting to prove this result unconditionally.\footnote{It would be
even more interesting to \emph{disprove} it, perhaps.}

\smallskip

\begin{proof
	Denote
	$$
	F_m(t) \ := \ \frac{1}{t^m} \, \sum_{k=1}^t \. k^m\..
	$$
	Let us prove now, that if the Kahn--Saks monotonicity conjecture holds, then we have:
	\begin{equation}\label{eq:OP-F-ineq}
		\Omega(P,t) \ \geq \ \prod_{x \in X} \. F_{b(x)-1}(t)\hskip.03cm.
	\end{equation}
To see this, first suppose that \hskip.03cm $r=1$, so the poset~$P$ has a unique maximal element $x$.
Thus, $b(x)=n$ \hskip.03cm in this case.
The number of order preserving functions for which $x$ has value $k$ is equal to \. $\Omega(P\smallsetminus x, t-k+1)$.
We have:	
$$
\Omega(P,t) \ = \ \sum_{k=1}^t \. \Omega(P \setminus x, k) \ \geq  \
\sum_{k=1}^t \. \Omega(P \smallsetminus x, t) \, \frac{k^{n-1}}{t^{n-1}} \ = \ \Omega(P \smallsetminus x, t) \. F_{b(x)-1}(t),
$$
where the inequality follows from the conjectured monotonicity. When \hskip.03cm $r\ge 2$,
the rest of the proof of~\eqref{eq:OP-F-ineq}
follows verbatim the proof of Theorem~\ref{thm:HP order poly}.
	
Now note the following bounded version of the \defng{Faulhaber's formula}:
$$
F_m(t) \, \geq \, \frac{t}{m} \. + \. \frac{1}{2} \quad \text{for all} \ \ m \geq 2.
$$
This inequality is well-known and can be easily proved by induction.
Substituting it into~\eqref{eq:OP-F-ineq}, gives the result.
\end{proof}

\smallskip

In support of this conjecture we prove the following partial result.

\smallskip

\begin{prop}
\label{prop:scaled}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements,
and let \hskip.03cm $k, \hskip.03cm t\in \mathbb N_{\ge 1}$\hskip.03cm. Then:
$$
\frac{1}{t^n} \, \Omega(P,t) \, \geq \, \frac{1}{(kt)^n} \, \Omega(P,kt)\hskip.03cm.
$$
Moreover, there is an injection which shows that the function \. $\Omega(P,t)\hskip.03cm k^n \hskip.03cm - \hskip.03cm \Omega(P,kt) \in {\textsc{\#P}}$.
\end{prop

\begin{proof}
Let \. $f \in {\mathbf{\Omega}}(P,kt)$. Consider an increasing function \hskip.03cm $g \in {\mathbf{\Omega}}(P,t)$ \hskip.03cm given by
$$g(x) \, := \, \left \lfloor \frac{f(x)-1}{k}\right\rfloor \. + \. 1,
$$
and let \hskip.03cm $\beta: X \to \{0,1,\ldots,k-1\}$ \hskip.03cm be given as the residue of~$f(x)$ modulo~$k$.
It is clear that the pair \hskip.03cm $(g,\beta)$ \hskip.03cm uniquely determines~$f$.
Then \. $\Omega(P,t)\hskip.03cm k^n \hskip.03cm - \hskip.03cm\Omega(P,kt)$ \. is the number of pairs \hskip.03cm $(g,\beta)$,
such that the map \hskip.03cm $h:X \to [n]$ \hskip.03cm given by \hskip.03cm $h(x) := k(g(x)-1) + \beta(x) +1$ \hskip.03cm
is not a linear extension, i.e.\ if \hskip.03cm $h(x) > h(y)$ \hskip.03cm for some \hskip.03cm $x\prec y$.
The last condition can be verified in polynomial time, proving that the difference is in~${\textsc{\#P}}$.
\end{proof}

\medskip

\subsection{Reverse monotonicity}\label{ss:OP-reverse-mono}
The following result at first appears counterintuitive until one
realizes that it's trivial asymptotically, when \hskip.03cm $t\to \infty$.
Just like the Kahn--Saks monotonicity conjecture, the small values
of~$t$ is where the difficulty occurs.

\smallskip

\begin{thm}\label{t:reverse-width}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset of width~$w$. Then the polynomial \.
$\Omega(P,t)/t^w$ \. is weakly increasing on all \. $t \in \mathbb N_{\ge 1}$\hskip.03cm.
\end{thm}

\smallskip

The proof is based on yet another application of the FKG inequality
in the following lemma of independent interest.

\smallskip

\begin{lemma}\label{lem:KS-mon}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset and let \hskip.03cm $t \geq k \ge 1$ \hskip.03cm be positive integers.
Then, for every minimal element $x$ of~$P$, we have:
	\begin{equation}\label{eq:KS-mon}
	\frac{\Omega(P,k)}{\Omega(P,t)} \ \leq \  \.  \frac{\Omega(P\setminus x,k)}{\Omega(P\setminus x,t)}\..
\end{equation}
\end{lemma}

\smallskip

\begin{proof}
Let \hskip.03cm $Y=\{x\}$ \hskip.03cm and \hskip.03cm $Z=X \setminus \{x\}$.
When $x$ is incomparable to every element of $Z$, we have
\begin{equation}\label{eq:OP-k-t}
	  \frac{\Omega(P,k)}{\Omega(P,t)} \ = \ \frac{k\. \Omega(P\setminus x,k)}{t\. \Omega(P\setminus x,t)}\.,
\end{equation}
and the result follows.

Thus, without loss of generality we can assume that \hskip.03cm $x \prec z$ \hskip.03cm for some \hskip.03cm $z \in Z$.
	Let \. $g,h: L \to \{0,1\}$ \. be given by
$$
	g(\textbf{\textit{v}})  \, := \, \left\{
\aligned\. 1 & \quad \text{if} \ \ v_x  \. \leq \. v_z \ \ \. \text{for all} \ \ z\in B(x), \, z\ne x \\
	\. 0 & \quad\text{otherwise}, \endaligned \right.
$$
$$
 h(\textbf{\textit{v}}) \, := \, \left\{ \aligned \. 1 & \quad \text{if} \ \  v_z \leq k \ \ \. \text{for all} \ \  z \in Z\\
	\. 0 & \quad \text{otherwise}. \endaligned\right.
$$
To show that \hskip.03cm $g$ \hskip.03cm is \hskip.03cm $\prec^{\small{\ts\diamond\ts}}$-decreasing,
it suffices to check that,
\begin{equation*
g(\textbf{w})\hskip.03cm =\hskip.03cm 1 \quad \text{and} \quad \textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w} \quad \Longrightarrow \quad  g(\textbf{\textit{v}})\hskip.03cm = \hskip.03cm 1.
\end{equation*}
Note that for every \hskip.03cm $z \in Z$ \hskip.03cm such that \hskip.03cm $x \prec z$, we have:
\[  v_x \ \leq \  w_x \ \leq \ w_z \ \leq \ v_z, \]
where the first and the third inequality is because \hskip.03cm $\textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w}$\hskip.03cm,
and the second inequality is because \hskip.03cm $g(\textbf{w})=1$.
This implies that \hskip.03cm $g(\textbf{\textit{v}})=1$, and thus \hskip.03cm $g$ \hskip.03cm is
a $\prec^{\small{\ts\diamond\ts}}$-decreasing function.

Similarly, to show that \hskip.03cm $h$ \t is $\prec^{\small{\ts\diamond\ts}}$-increasing,
it suffices to check that
\begin{equation*
h(\textbf{\textit{v}})\hskip.03cm =\hskip.03cm 1 \quad \text{and} \quad \textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w} \quad \Longrightarrow \quad  h(\textbf{w})\hskip.03cm = \hskip.03cm 1.
\end{equation*}
Note that for every \hskip.03cm $z \in Z$, we have:
\[  w_z \ \leq \  v_z \ \leq \ k, \]
where the first  inequality is because \hskip.03cm $\textbf{\textit{v}} \prec^{\small{\ts\diamond\ts}} \textbf{w}$\hskip.03cm, and the second inequality is because \hskip.03cm $h(\textbf{\textit{v}})=1$.
This implies that \hskip.03cm $h(\textbf{w})=1$, and thus \hskip.03cm $h$ \hskip.03cm is a $\prec^{\small{\ts\diamond\ts}}$-increasing function.

		Now observe that the um \hskip.03cm
		$E(gh)$ \hskip.03cm counts \hskip.03cm $\textbf{\textit{v}} \in L$ \hskip.03cm for which \hskip.03cm
		$v_x \leq k$. Indeed, by the assumption there exist \hskip.03cm $z \in Z$,
such that \hskip.03cm $x \prec z$.  This implies
		\[ v_x \ \leq \ v_z \ \leq \ k, \]
		where the first inequality is because \. $g(\textbf{\textit{v}})=1$\., and the second inequality is because \. $h(\textbf{\textit{v}})=1$.
		Thus, \hskip.03cm $E(gh)$ counts the number of order preserving maps \. $f: X \to [k]$, i.e.  $E(gh)=\Omega(P,k)$.
		It is also straightforward to verify that
		\begin{align*}
			E(g)  \, = \, \Omega(P,t), \quad E(h) \, = \,  t \. \Omega(P \setminus x,k) \quad \text{and}
\quad E(\textbf{1}) \, = \, t \. \Omega(P\setminus x,t).
		\end{align*}
The lemma now  follows from the FKG inequality~(Theorem~\ref{thm:FKG}).
\end{proof}

\smallskip


\begin{proof}[Proof of Theorem~\ref{t:reverse-width}]
Let \hskip.03cm $H$ \hskip.03cm be a maximal antichain in \hskip.03cm $P$ \hskip.03cm of width~$w$.
Note that Lemma~\ref{lem:KS-mon} can also be applied to maximal
elements~$x$ of~$P$, by considering the dual poset \hskip.03cm $P^\ast$.
Now, by consecutively removing elements in \hskip.03cm $X \setminus H$,
by Lemma~\ref{lem:KS-mon}, we get
	\begin{equation*}
	\frac{\Omega(P,k)}{\Omega(P,t)} \ \leq \  \.  \frac{\Omega(P',k)}{\Omega(P',t)} \ = \  \frac{k^{w}}{t^{w}}\,,
\end{equation*}
where \hskip.03cm $P'=P|_H$ \hskip.03cm is the subposet of $P$ restricted to~$H$.
This implies the result.
\end{proof}

\smallskip

We conclude with another conjecture motivated by~\eqref{eq:OP-k-t} in the proof of Lemma~\ref{lem:KS-mon}.


\smallskip

\begin{conj}\label{conj:KS-FKG}
	Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset, and let
\. $t \geq k\ge 1$ \. be positive integers.
	Then there exists \hskip.03cm $x \in X$, such that
	\begin{equation}\label{eq:KS-FKG}
	  \frac{\Omega(P,k)}{\Omega(P,t)} \ \geq \  \frac{k\. \Omega(P\setminus x,k)}{t\. \Omega(P\setminus x,t)}.
	\end{equation}
\end{conj}

\smallskip

\begin{prop}
Conjecture~\ref{conj:KS-FKG} \hskip.03cm implies \hskip.03cm
Conjecture~\ref{conj:KS-mon}.
\end{prop}

\smallskip

The proof of this proposition follows the proof of the theorem above.

\medskip

\subsection{Graham conjecture}\label{ss:OP-Graham}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm on \hskip.03cm $|X|=n$ elements.
Fix element \hskip.03cm $x\in X$ \hskip.03cm and an integer \hskip.03cm $t\ge 1$.
Denote by \hskip.03cm $\Omega(P,t; \hskip.03cm x,a)$ \hskip.03cm the number of order preserving
maps \hskip.03cm $g: X\to [t]$, such that \hskip.03cm $g(x)=a$.  In \cite[p.~129]{Gra},
by analogy with Stanley's inequality~\eqref{eq:Sta}, Graham made in passing the
following conjecture:

\smallskip

\begin{conj}[{\em \defn{\rm Graham's conjecture}}{}]\label{conj:Graham}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset, and
let \hskip.03cm $x\in X$, let \hskip.03cm $a, \hskip.03cm t\in \mathbb N_{\ge 1}$, and suppose \hskip.03cm $1< a < t$.
Then:
$$
\Omega(P,t; \hskip.03cm x,a)^2 \, \ge \, \Omega(P,t; \hskip.03cm x,a+1) \. \cdot \. \Omega(P,t; \hskip.03cm x,a-1).
$$
\end{conj}

\smallskip

The following result shows that  holds asymptotically.

\smallskip

\begin{thm}\label{t:Graham-asy}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a finite poset, and let \hskip.03cm $x\in X$.
Then, for every \hskip.03cm $a\in \mathbb N_{\ge 1}$\hskip.03cm,
	there exists an integer  \. $T(P,x,a)>0$ \. such that, for all \. $t > T(P,x,a)$, we have:
	 $$
	 \Omega(P,t; \hskip.03cm x,a)^2 \, \ge \, \Omega(P,t; \hskip.03cm x,a+1) \. \cdot \. \Omega(P,t; \hskip.03cm x,a-1).
	 $$
\end{thm}

\smallskip


\begin{proof}
Fix an integer \hskip.03cm $a\ge 1$.  Denote by \.
$D:=\{y\in X \.:\.y \preccurlyeq x\}$ \. the lower order ideal of~$x$, and
let \hskip.03cm $d:=|D|$.
Observe that \. $\Omega(P,t; \hskip.03cm x,a)$ \. is a polynomial in~$\hskip.03cm t$ \hskip.03cm
	with the leading term
$$
\Omega(D-x,a)  \, \frac{e(P\smallsetminus D)}{(n-d)!} \ t^{n-d}\..
$$
Indeed, for every $\prec$-increasing function \hskip.03cm $g: X\to [t]$,
we have \hskip.03cm $g(y)\le a$ \hskip.03cm for all \hskip.03cm $y\in D$, which explains
the term \hskip.03cm $\Omega(D-x,a)$.  For the remaining elements
\hskip.03cm $z\in X\smallsetminus D$, we have no such restrictions as \hskip.03cm $t\to \infty$,
and the number of such functions is asymptotically \hskip.03cm $\sim e(P\smallsetminus D) \. t^{n-d}/(n-d)!$

Therefore, as \hskip.03cm $t\to \infty$, the leading coefficient  of the polynomial
$$\Omega(P,t; \hskip.03cm x,a)^2 \, - \, \Omega(P,t; \hskip.03cm x,a+1) \. \cdot \. \Omega(P,t; \hskip.03cm x,a-1)
$$
is equal to
\[
\Big[\Omega(D-x,a)^2 \. - \.  \Omega(D-x,a+1) \.
\Omega(D-x,a-1) \Big] \, \frac{e(P-D)}{(n-d)!}\..  \]
This is strictly positive by Theorem~\ref{thm:log-concave-strict},
which implies the result.
\end{proof}

\smallskip

As a further evidence in favor of the conjecture,
we present the following variation.

\smallskip

\begin{thm}
	For every \hskip.03cm $x \in X$ \hskip.03cm and integers \hskip.03cm $t> a >1$, we have:
	$$
	\Omega(P,t; \hskip.03cm x,a+1) \. \cdot \.\Omega(P,t; \hskip.03cm x,a) \, \ge \,
\Omega(P,t+1; \hskip.03cm x,a+1) \. \cdot \. \Omega(P,t-1; \hskip.03cm x,a).
	$$
\end{thm}


\begin{proof}
The proof follows from the same argument as in Theorem~\ref{thm:log-concave}.
In this case, replace Shepp's lattice \hskip.03cm ${\mathcal{L}}$ \hskip.03cm with a sublattice \.
${\mathcal{L}}_{x,a} \hskip.03cm := \hskip.03cm \{ \textbf{\textit{v}} \in L \. : \. \textbf{\textit{v}}_x=a\}$.  Define functions
\hskip.03cm $g,\hskip.03cm h, \hskip.03cm \mu$ \hskip.03cm as in the proof of Theorem~\ref{thm:log-concave},
and proceed verbatim.  We omit the details.
\end{proof}

\medskip

\section{Bounds on the $q$-analogue} \label{s:q-analogue}

In this section we study the $q$-order polynomial generalization.
First, we present Reiner's short proof of the Bj\"orner--Wachs inequality.
Then, we give $q$-analogue of Shepp's inequality and study its consequences.

\subsection{Reiner's inequality}\label{ss:q-analogue-Reiner}
Most recently, Vic Reiner shared with us the following elegant approach
to the Bj\"orner--Wachs inequality which we reproduce with his
permission.\footnote{Vic Reiner, personal communication, March~17, 2022. }

\smallskip

\begin{thm}[{\rm Reiner, 2022}] \label{t:HP-q}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.
Denote by \. $\mathcal R(P)$ \. the set of all weakly order-preserving maps \.
$g: X\to \mathbb N$, i.e.\ \. $g(x)\le g(y)$ \. for all \. $x\prec y$.
Let \. $|g| \hskip.03cm := \hskip.03cm \sum_{x\in X} \hskip.03cm g(X)$.
Then:
\begin{equation}\label{eq:HP-q}
\sum_{g\in \mathcal R(P)} \. q^{|g|} \ \geqslant_q  \  \. \prod_{x \hskip.03cm \in X} \, \frac{1}{1-q^{b(x)}}\,,
\end{equation}
where the inequality between two power series is coefficient-wise.
\end{thm}

\smallskip

Theorem~\ref{t:HP} follows from \defng{$P$-partition theory} of Stanley,
see~\cite[$\S$3.15]{Sta-EC}.  Indeed, recall that
$$
\sum_{g\in \mathcal R(P)} \. q^{|g|} \, = \, \frac{F_P(q)}{(1-q)(1-q^2)\cdots (1-q^n)}\,,
$$
such that \hskip.03cm $F_P(1)=e(P)$.  Here \hskip.03cm $F_P(q)$ \hskip.03cm denotes the sum of \hskip.03cm
$q^{\mathrm{maj}(f)}$ \hskip.03cm over all \hskip.03cm $f\in \Ec(P)$, see~\cite{Sta-EC} for the
details.\footnote{The notation in~\cite{Sta-EC} is different but equivalent;
we change it for simplicity since the \defng{major index} plays only tangential
role in this paper.  There is also a minor subtlety here, that
\defng{Stanley's P-partition theory} requires \emph{natural
labeling} of~$X$, cf.~$\S$\ref{s:OP-inj}. }
Taking \hskip.03cm $0< q <1$, multiplying both sides of~\eqref{eq:HP-q} by
\. $(1-q)(1-q^2)\cdots (1-q^n)$, and taking the limit \. $q\to 1-$, gives the
Bj\"orner--Wachs inequality~\eqref{eq:HP}.

\smallskip

\begin{proof}[Proof of Theorem~\ref{t:HP-q}]
Interpret the RHS of~\eqref{eq:HP-q} as the GF for maps \. $g\in \mathcal R(P)$ \. which
are obtained as a nonnegative integer linear combination of the characteristic
functions of upper order ideals:
$$g \.= \, \sum_{x\in X} \, m(x) \.\chi_{B(x)}\., \ \ \. \text{where} \ \ m(x) \in \mathbb N \ \ \text{for all} \ \ x\in X.
$$
Note that characteristic functions \hskip.03cm $\chi_{B(x)}$ \hskip.03cm are linearly independent
because in the standard basis \hskip.03cm $\chi_{y}$, \hskip.03cm $y\in X$, the transition matrix is unitriangular.
Since now \. $|g| = \sum_{x\in X} \. m(x) \. b(x)$, the result follows immediately.
\end{proof}

\smallskip

\begin{ex}
Consider a poset \hskip.03cm $P=(X,\prec)$ \hskip.03cm with \hskip.03cm $X=\{a,b,c,d\}$ \hskip.03cm
and \hskip.03cm  $a\prec b,c \prec d$, so \hskip.03cm $P\simeq C_2\times C_2$.
The RHS of~\eqref{eq:HP-q} as in the proof
above is the GF for \hskip.03cm $g\in \mathcal R(P)$, such that \hskip.03cm $g(a)+g(d) \ge g(b) + g(c)$.
Not all \hskip.03cm $g\in \mathcal R(P)$ \hskip.03cm satisfy this property, e.g.\ $g(a)=0$, \hskip.03cm
$g(b)=g(c)=g(d)=1$ \hskip.03cm does not.
\end{ex}
\smallskip

\begin{rem}\label{r:G-M}
In principle, there is a way to convert the natural injection as in
the proof above into an injection as in Proposition~\ref{p:HP-injection}.
The idea is to make the multiplication by \. $(1-q)\cdots (1-q^n)$ \.
to be effective by using the \defng{involution principle} of Garsia
and Milne~\cite{GM}.  See also~\cite{Gre} which comes closest in this
special case.  Note that the resulting maps tend to be hard
to compute, sometimes provably so, see e.g.~\cite{KP}.
\end{rem}

\smallskip

\subsection{$q$-order polynomial} \label{ss:q-analogue-our}
For an integer \hskip.03cm $t\ge 1$, define
$$\Omega_q(P,t) \, : = \, \sum_{g} \ q^{|g|-n}
$$
where the summation is over all order preserving maps \. $g: X\to [t]=\{1,\ldots,t\}$,
i.e.\ maps which satisfy \. $g(x)\le g(y)$ \. for all \. $x \prec y$.
This is the \defn{$q$-order polynomial}
corresponding to poset~$P$, see e.g.~\cite{Cha}.  Let us emphasize that here~$q$
is a formal variable, while \hskip.03cm $t\ge 1$ \hskip.03cm is an integer.


\smallskip

\begin{thm}[{\rm {\em{\defn{$q$-analogue of Shepp's inequality}}}}]\label{t:FKG-OP-q}
Let \hskip.03cm $A$ \hskip.03cm be the collection defined in \S\ref{ss:OP-induction-prelim}, and let \hskip.03cm $C,C'$ \hskip.03cm
be $Y$-minimizing collections w.r.t.\ partition \ $X=Y\sqcup Z$. Then,
\[
\Omega_q \big(C  \cap   C' \cap A,\hskip.03cm t\big)  \. \cdot \.  \Omega_q\big(A,\hskip.03cm t\big)
\quad \geqslant_q \quad \Omega_q \big(C \cap A,\hskip.03cm t\big)  \. \cdot \.  \Omega_q\big( C' \cap A,\hskip.03cm t\big)\.,	
\]
where the inequality holds coefficient-wise as a polynomial in~$q$,
for all integer \hskip.03cm $t\ge 1$.
\end{thm}

\smallskip

The proof follows the original proof in~\cite{She}, with  the following \defng{$q$-FKG inequality} by Bj\"orner~\cite{Bjo}.
Let \. $L:=(L,\prec^{\small{\ts\diamond\ts}})$ \. be a distributive lattice.
A function \. $r:L \to \Rb_{\geq 0}$ \. is called \hskip.03cm \defn{modular} \hskip.03cm if
\[ r(a) \. + \.   r(b) \ = \  r(a \wedge b) \. + \.  r(a \vee b) \quad \text{ for every } \. a,b \in L. \]

\smallskip

\begin{thm}[{\rm {\em{\defn{$q$-FKG inequality}}}, \cite[Thm~2.1]{Bjo}}]\label{thm:q-FKG}
Let \hskip.03cm ${\mathcal{L}} =(L,\prec)$ \hskip.03cm be a finite distributive lattice,
let \. $\mu: L \to \Rb_{\geq 0}$ \. be a log-supermodular function, and let
\. $r:L \to \Rb_{\geq 0}$ \. be a modular function.
	Then, for every pair of $\prec^{\small{\ts\diamond\ts}}$-decreasing functions \. $g,h: L \to \Rb_{\geq 0}$, we have:
	\[ E_q(\textbf{\em 1}) \. E_q(gh) \ \geqslant_{q} \  E_q(g) \. E_q(h), \]
	where the inequality holds coefficient-wise as a polynomial in $q$, \.
	where
	\[ E_{q}(g) \, = \, E_{q}(g;\mu,r) \ := \  \sum_{a \in L} g(x) \. \mu(x) \. q^{r(x)},
\]
and \. $\textbf{\em 1}:L \to \Rb$ \. is given by \. $\textbf{\em 1}(a)=1$ \. for all \hskip.03cm $a \in L$.
\end{thm}

\smallskip

\begin{rem}\label{r:Bjorner}
Note that Theorem 2.1 in \cite{Bjo} assumes that \. $r:L \to \Rb_{\geq 0}$  \.
is the \emph{rank function} of the lattice~$L$. It is however straightforward
to show that the same proof still works when applied to any modular function~$\hskip.03cm r$.
\end{rem}

\smallskip

\begin{proof}[Proof of Theorem~\ref{t:FKG-OP-q}]
	The proof follows the same argument as in  the proof of Lemma~\ref{t:FKG order polynomial},
	with the FKG inequality being replaced with Theorem~\ref{thm:q-FKG} applied to the modular function
	 \. $r:L \to \Rb_{\geq 0}$ \.  given by \. $r(\textbf{\textit{v}}) \. := \. \sum_{x \in X} v_x$\..
\end{proof}

\smallskip


\begin{cor}\label{cor:main OP-q}
	Let \. $P=(X,\prec)$ \. be a poset, and let \. $x,y\in X$ \. be minimal elements.
	Then, for all \hskip.03cm $t\in \mathbb N_{\ge 1}$ \hskip.03cm and \hskip.03cm $q\in \mathbb R_+$, we have:
	\[ {\Omega_q\big(P,\hskip.03cm t\big)} \. \cdot \. {\Omega_q\big(P \smallsetminus \{x,y\},\hskip.03cm t\big)}
\ \geq \  {\Omega_q\big(P \smallsetminus x, \hskip.03cm t\big)}  \. \cdot \.  {\Omega_q\big(P\smallsetminus y,\hskip.03cm t\big)}.
	\]
\end{cor}

\begin{proof}
Denote \. $(n)_q \hskip.03cm :=  \hskip.03cm 1+q+\ldots + q^{n-1}$.
	Let $C$ and $C'$ be as in \eqref{eq:colC}, and $A$ be as in \eqref{eq:colA}.
	Observe that
	\begin{alignat*}{2}
		& \Omega_q(C \cap C' \cap A,t) \ = \ \Omega_q(P,t), \qquad  &&  \Omega_q(C' \cap A,t) \ = \ q \hskip.03cm (t)_q \. \Omega_q(P\smallsetminus x,t),\\
		&  \Omega_q(C \cap A,t) \ = \ q \hskip.03cm (t)_q \. \Omega_q(P \smallsetminus y,t), \qquad  &&  \Omega_q(A,t) \ = \ q^2 \hskip.03cm (t)_q^2 \.\hskip.03cm \Omega_q(P \smallsetminus \{x,y\},t).
	\end{alignat*}
	The conclusion of the lemma now follows from  Theorem~\ref{t:FKG-OP-q}
	and the equation above.
\end{proof}

\smallskip

\begin{rem}\label{r:q-analogue}
Note that our proof does not show that the inequality in Corollary~\ref{cor:main OP-q} holds
 coefficient-wise as a polynomial in~$q$,
 since the derivation involves canceling the term \hskip.03cm $q\hskip.03cm (t)_q$.
It remains to be seen if a $q$-analogue of Theorem~\ref{thm:HP order poly} exists,
which hinges on finding an appropriate $q$-analogue for Lemma~\ref{l:main order polynomial}.
\end{rem}

\smallskip

We also have the following \defng{$q$-log-concavity} for order polynomials.

\smallskip

\begin{cor}\label{c:q-log-concavity}
	Let $P=(X,\prec)$ be a finite poset.
Then, for every integer $t \geq 2$,
\[ \Omega_q(P,t)^2  \  \geqslant_q \ \Omega_q(P,t+1) \. \cdot \. \Omega_q(P,t-1),\]
where the inequality holds coefficient-wise as a polynomial in~$q$.
\end{cor}

\begin{proof}
		The proof follows the same argument as in  the proof of Theorem~\ref{thm:log-concave},
	with the FKG inequality being replaced with Theorem~\ref{thm:q-FKG} applied to the modular function
	\. $r:L \to \Rb_{\geq 0}$ \.  given by \. $r(\textbf{\textit{v}}) \. := \. \sum_{x \in X} v_x$\..
\end{proof}


\bigskip


\section{Bounding the order polynomial by injection} \label{s:OP-inj}


\smallskip

Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset with \hskip.03cm $|X|=n$ \hskip.03cm elements.
Denote by \hskip.03cm ${\mathbf{\Omega}}(P,t)$ \hskip.03cm the set of order preserving maps \hskip.03cm $P \to [t]$, so that \. $\Omega(P,t)=|{\mathbf{\Omega}}(P,t)|$.
Fix a \defn{natural labeling} of $X$, i.e.\ write \. $X=\{x_1,\ldots,x_n\}$, where \. $i<j$ \. for all \. $x_i \prec x_j$.


For a sequence \. $(a_1,\ldots,a_k)$ \. of distinct integers, a \defn{standardization}
is a permutation \. $\sigma=(\sigma_1,\ldots,\sigma_k)\in S_k$ \. with integers in the same
relative order:
$$
a_i < a_j \ \Leftrightarrow \ \sigma_i < \sigma_j \quad \text{for all} \quad 1\le i < j \le k\hskip.03cm.
$$
For example, the standardization of \. $(4,7,6,3)$ \. is \. $(2,4,3,1)\in S_4$.

\smallskip

\begin{proof}[Proof of Theorem~\ref{thm:order_le}]
We construct an injection
$$\Psi: \, \Ec(P) \hskip.03cm \times \hskip.03cm [t]^n \. \to \ {\mathbf{\Omega}}(P,t) \hskip.03cm \times \hskip.03cm S_n\hskip.03cm.
$$
One can think of \. $[t]^n$ \. as an \emph{ordered set partition}
$$
[n] \ = \ B_1 \. \sqcup \. \ldots \. \sqcup B_t\.,
$$
where \. $B_i\subseteq [n]$ \. can be empty.  We use \. $\beta=(B_1,\ldots,B_t)$ \. to denote this ordered
set partition.


Let \. $f \in \Ec(P)$ \. be a linear extension, and \. $\beta=(B_1,\ldots,B_t)$ \.
be an ordered set partition as above.  Denote \. $b_i := |B_i|$,
where \. $1 \le i \le t$.  Let \. $\alpha = (a_1,\ldots,a_n)\in [t]^n$ \.
be a weakly increasing sequence
$$
\big(1,\ldots, 1, \ 2,\ldots, 2, \ \ \ldots \ \  , \ t, \ldots, t\big) \ \ \,
\text{with \. $b_i$ \. copies of \. $i$, \ for all \. $1\le i \le t$}\hskip.03cm.
$$
By abuse of notation, we also use \hskip.03cm $\alpha$ \hskip.03cm to denote a function \. $\alpha: [n]\to [t]$ \. given by \.
$\alpha(i):=a_i$.


Define a function \. $g: \hskip.03cm X \to [t]$ \. as \. $g(x_i) := \alpha\bigl(f(x_i)\bigr)$,
so that elements \. $f^{-1}(1)$, \ldots, $f^{-1}(b_1)$ are assigned value~$1$, elements \.
$f^{-1}(b_1+1)$, \ldots, $f^{-1}(b_1+b_2)$ are assigned value~$2$, etc. Observe that \.
$g \in {\mathbf{\Omega}}(P,t)$ \. since~$\hskip.03cm f$ \hskip.03cm is increasing with respect to the poset order, and~$\hskip.03cm \alpha$
is a weakly increasing function.

Next, define a permutation \. $\sigma\in S_n$ \. as follows. For each~$i$,
let \. $g^{-1}(i) = \big\{x_{i_1},\ldots,x_{i_k}\big\}$, where \. $i_1<\ldots<i_k$ \. and \hskip.03cm $k=b_i$ \hskip.03cm by construction.
Let \hskip.03cm $s^{(i)} \in S_k$ \hskip.03cm be the standardization of the sequence \. $\bigl(f(x_{i_1}),\ldots, f(x_{i_k})\bigr)$.
Now, rearrange the elements in \hskip.03cm $B_i$ \hskip.03cm according to~$s^{(i)}$, obtaining a sequence \.
$\gamma_{i}$ \.
whose standardization is~$s^{(i)}$.
The permutation $\sigma$ is then obtained by concatenating the resulting sequences, i.e.
$\sigma:=\gamma_{1} \gamma_{2}\ldots \gamma_{t} \in S_n$.
Finally, define \. $\Psi(f,\beta) := (g, \sigma)$.

\smallskip

To prove that \hskip.03cm $\Psi$ \hskip.03cm is an injection, we construct an inverse map \hskip.03cm $\Psi^{-1}$.
Let \. $g \in \Omega(P,t)$ \. and \. $\sigma \in S_n$. Denote  \. $c_i :=|g^{-1}(i)|$,
for all \. $1\le i \le t$.  Let \. $\tau\in [t]^n$ \. be the sorted
sequence of values that the function~$g$ takes, i.e.\
$$\tau \ := \ \big(1,\ldots, 1, \ 2,\ldots, 2, \ \ \ldots \ \  , \ t, \ldots, t\big) \ \ \, \text{with \.
$c_i$ \. copies of \. $i$, \ for all \. $1\le i \le t$}\hskip.03cm.
$$
Note that \hskip.03cm $\tau$ \hskip.03cm is the weakly increasing.
For each $i$, let
$$
C_i \ := \ \big\{\sigma_{c_1\hskip.03cm+\hskip.03cm\ldots \hskip.03cm+\hskip.03cm c_{i-1}\hskip.03cm+\ts1} \., \. \ldots \., \. \sigma_{c_1\hskip.03cm+\hskip.03cm\ldots \hskip.03cm+\hskip.03cm c_i}\big\}
$$
consisting of a block of size $c_i$ of entries from~$\sigma$.
Denote by \. $\pi=(C_1,\ldots,C_t)$ \. the resulting ordered partition.

Finally, define a function \.
$h: X\to [n]$ \. obtained by rearranging the values on the $c_i$ elements in~$g^{-1}(i)$
according to the ordering in \.
$$
\big(\sigma_{c_1\hskip.03cm+\hskip.03cm\ldots \hskip.03cm+\hskip.03cm c_{i-1}\hskip.03cm+\ts1} \., \. \ldots \., \.  \sigma_{c_1\hskip.03cm+\hskip.03cm\ldots \hskip.03cm+\hskip.03cm c_i}\big),
$$
i.e., so that their standardizations are the same permutations.
Let us emphasize that \hskip.03cm $h$ \hskip.03cm
is not necessarily a linear extension for general \hskip.03cm $(g,\sigma)$ \hskip.03cm as above.

Now take \. $\Psi^{-1} := (h,\pi)$, and observe that
$$
\Psi^{-1}\bigl(\Psi(f,\beta)\bigr) \, = \, (f,\beta)
$$
by construction.  This completes the proof.
\end{proof}

\smallskip

\begin{ex}
Let us illustrate the construction of \. $\Psi(f,\beta)=(g,\sigma)$ \. in the proof above.
Let \. $P=(X,\prec)$ \. be a poset on \hskip.03cm $n=7$ \. elements as in
Figure~\ref{f:injection}, where
\. $X=\{x_1,\ldots,x_7\}$ \. with the partial order~$\prec$ increasing downwards.
Note that we chose a natural labeling, see above.

Suppose \hskip.03cm $t=3$.  Let \hskip.03cm $f\in \Ec(P)$ \hskip.03cm be a linear extension as in the figure, and let
\. $\beta=(B_1,B_2,B_3)$, where \. $B_1=\{2,3,7\}$,
$B_2=\{4,6\}$ \. and \. $B_3 = \{1,5\}$. Then we have \. $\alpha = (1,1,1,2,2,3,3)$ \. and
the order preserving function \hskip.03cm $g$ \hskip.03cm is given as in the figure.  Then,
standardize the values \.
$$\aligned
& \hskip2.cm\bigl(f(x_1),f(x_3),f(x_5)\bigr) = (2,1,3) \  \longrightarrow \ (2,1,3)\.,\\
& \bigl(f(x_2),f(x_7)\bigr) = (4,5) \   \longrightarrow \ (1,2)\., \qquad
\bigl(f(x_4),f(x_6)\bigr) = (6,7) \  \longrightarrow \ (1,2).
\endaligned
$$
Permute the elements within \. $B_1,B_2,B_3$ \. accordingly to get \. $\gamma_1 = (3,2,7)$, \. $\gamma_2=(4,6)$ \.
 and \. $\gamma_3 = (1,5)$.  Concatenating these, we obtain \. $\sigma = (3,2,7,4,6,1,5)\in S_7$.

\smallskip

In the opposite direction, let \. $g'\in {\mathbf{\Omega}}(P,3)$ \. be as in Figure~\ref{f:injection}, and let \.
$\sigma=(7,1,3,2,5,4,6)$.
Then \. $\tau=(1,1,2,2,3,3,3)$, so \. $c_1=c_2=2$ \. and \. $c_3=3$.
This gives \. $C_1=\{1,7\}$, \. $C_2=\{2,3\}$ \. and
\. $C_3=\{4,5,6\}$.  The corresponding reduced permutations are then \. $(2,1)$, \. $(2,1)$ \.
and \. $(2,1,3)$, respectively, giving a map \. $h: X\to [t]$.  Finally, note that \. $h\notin \Ec(P)$ \.
in this case.
\end{ex}

\begin{figure}[hbt]
\begin{center}
\includegraphics[width=16.5cm]{Injection1}
\end{center}
\vskip-.3cm
\caption{An example of the injection $\Psi$ and the inverse map $\Psi^{-1}$. }\label{f:injection}
\vskip.3cm
\end{figure}


\smallskip

\begin{proof}[{Proof of Theorem~\ref{t:OP-SP}}]
In the notation of the proof above, let \. $(g,\sigma) \in {\mathbf{\Omega}}(P,t) \times S_n$ \.
and let \. $(h,\pi) =  \Psi^{-1}(g,\sigma)$.   By construction, we have \.
$(h,\pi) \in \Ec(P) \times [t^n]$ \.  if and only if \. $h \in \Ec(P)$.
Thus, the function  \. ${\zeta}(P,t)$ \. is equal to the number of  \.
$(g,\sigma) \in {\mathbf{\Omega}}(P,t) \times S_n$ \. such that \hskip.03cm $h \notin \Ec(P)$.
Since \hskip.03cm $\Psi^{-1}$ \hskip.03cm can be computed in polynomial time, this
implies the result.
\end{proof}

\smallskip

\begin{ex}\label{e:HP-power}
Let \. $P= A_{n}$ \. be an antichain on \hskip.03cm $n$ \hskip.03cm elements.
Then we have \. $e(A_n)=n!$ \. and \. $\Omega(A_n,t)=t^n$.
In this case both~\eqref{eq:OP-HP} and~\eqref{eq:OP-gen} are equalities.
Similarly, let \hskip.03cm $P=C_n$ \hskip.03cm be a chain of $n$ elements. Then we have \.
$e(C_n)=1$ \. and \. $\Omega(P,t) = \binom{t+n-1}{n}$.  In this case,
the lower bound~\eqref{eq:OP-HP} is slightly better than~\eqref{eq:OP-gen}.
\end{ex}

\smallskip

In a different direction, here are equality conditions for~\eqref{eq:OP-gen} in
Theorem~\ref{thm:order_le}.

\smallskip

\begin{cor}\label{c:OP2-equality}
Let \hskip.03cm $P=(X,\prec)$ \hskip.03cm be a poset on \hskip.03cm $|X|=n$ \hskip.03cm elements.  Then
$$
\Omega(P,t) \, = \, e(P) \. \frac{t^n}{n!}
$$
for some \. $t \in\mathbb N_{\ge 1}$ \. \underline{if and only if} \. $P=A_n$ \hskip.03cm
is a $n$-antichain.
\end{cor}

\begin{proof}
The ``if'' part is clear.
\hskip.03cm
For the ``only if'' part, suppose that \hskip.03cm $P \neq A_n$.
Then there are \hskip.03cm $x_i, x_{i+1}\in X$ \hskip.03cm such that \hskip.03cm $x_i\prec x_{i+1}$,
and \hskip.03cm $x_{i+1}$ covers~$x_i$.  Without loss of generality,
we can assume that \hskip.03cm $x_i$ \hskip.03cm is a minimal element.

It follows from the proof of Theorem~\ref{thm:order_le},
that equality in~\eqref{eq:OP-gen} holds \hskip.03cm if and only if \hskip.03cm
$\Psi$ is a bijection. In particular,  for all  \.$(g,\sigma) \in {\mathbf{\Omega}}(P,t) \times S_n$ \.
the map \hskip.03cm $h$ \hskip.03cm in \. $\Psi^{-1}(g, \sigma) = (h,\pi)$ \. must be a linear extension.
Now take an order preserving map~$g$, such that \. $g(x_1)=\ldots=g(x_{i+1})=1$,
and \hskip.03cm $\sigma = (i,i+1)$. Then we have \hskip.03cm $h(x_i)=i+1$ \hskip.03cm and \hskip.03cm $h(x_{i+1})=i$,
so that \hskip.03cm $h\notin \Ec(P)$ \hskip.03cm is not a linear extension. Thus, map~$\Psi$ is not a
bijection in this case.
This completes the proof.
\end{proof}

\smallskip

\begin{ex}\label{e:OP-Stanley}
Let \. $P_n = C_1 \oplus A_{n-1}$ \. be an ordered tree poset consisting of one minimal element
and $(n-1)$ maximal elements.  Then \hskip.03cm $e(P)=(n-1)!$ \hskip.03cm and the bound~\eqref{eq:HP} is an equality.
Observe that
$$
\Omega(P_n,t) \ = \ 1^{n-1}\. + \. 2^{n-1}\. + \. \ldots \. + \.  t^{n-1} \ = \ \frac{t^n}{n} +  \frac{t^{n-1}}{2} +   O(t^{n-1}).
$$
The general inequality~\eqref{eq:OP-gen} gives \. $\Omega(P_n,t) \hskip.03cm \ge \ \frac{t^n}{n}$\hskip.03cm,
while~\eqref{eq:OP-HP} gives a stronger bound:
$$
\Omega(P_n,t) \ \ge \ \frac{1}{n} \. \bigl(t^n + \.t^{n-1}\bigr).
$$
Asymptotically, both lower bounds are not tight in the second order term.
Compare this to~\eqref{eq:OP-F-ineq} which conjecturally gives a sharp bound.
\end{ex}

\smallskip

\begin{rem}\label{r:OP-injection}
Neither of the Theorems~\ref{thm:HP order poly} and~\ref{thm:order_le} imply each other.
Note that the leading coefficient of \hskip.03cm $\Omega(P,t)$ \hskip.03cm is \hskip.03cm $e(P)/n!$,
and the Bj\"orner--Wachs inequality~\eqref{eq:HP} is an equality only for
ordered forests (Proposition~\ref{p:HP-forest}). Thus, for large values of~$t$,
the lower bound in Theorem~\ref{thm:order_le} asymptotically better.

On the other hand, the lower bound in Theorem~\ref{thm:order_le} cannot
be improved to \. $t^r\hskip.03cm (t+1)^{n-r}\hskip.03cm e(P)/n!$ \. as Theorem~\ref{thm:HP order poly}
might suggest.  Indeed, for the poset $P_n$ as in the example above, we have:
$$\Omega(P_n,2) \ = \ 1^{n-1}+2^{n-1} \ < \ \frac{2\cdot 3^{n-1}}{n} \quad \ \text{for \ $n\geq 3$.}
$$

Finally, let us mention that the order polynomial \hskip.03cm $\Omega(P,t)$ \hskip.03cm can have
negative coefficients, implying that~\eqref{eq:OP-gen} does not follow directly
from the leading term of \. $t^n e(P)/n!$ \.  For example, recall that
$$
\Omega(P_5,t) \ = \
1^{4}\. + \. 2^{4} \. + \. \ldots \. +  \. t^{4} \ = \ \frac{1}{30}\.
\bigl(6 \hskip.03cm t^5 \hskip.03cm + \hskip.03cm 15 \hskip.03cm t^4 \hskip.03cm + \hskip.03cm 10 \hskip.03cm t^3 \hskip.03cm - \hskip.03cm t\bigr),
$$
and note the negative coefficient in~$t$.
\end{rem}

\medskip


\section{Restricted linear extensions} \label{s:restricted}

In this section we use an algebraic approach to obtain vanishing and uniqueness
conditions for the generalized Stanley inequality.  We also present a direct
combinatorial argument for the uniqueness conditions.

\subsection{Background}\label{ss:restricted-background}
Before we proceed to generalizations, let us recall some definition
and results about group action on the set~$\Ec(P)$ of linear extensions.
In our presentation we follow Stanley's survey~\cite{Sta-promo}.

Let \hskip.03cm $X=(X,\prec)$ \hskip.03cm be a poset on \hskip.03cm $|X|=n$ \hskip.03cm elements.
A \defn{promotion} \. $\partial: \Ec(P) \to \Ec(P)$  \. is a bijection
on linear extensions defined as follows.  For \hskip.03cm $f\in \Ec(P)$,
let \. $t_1 \prec \ldots \prec t_r$ \.
be a maximal chain in~$P$, such that $f(t_1),f(t_2),\ldots,f(t_r)$ is
lexicographically smallest. Define \. $f\partial\in \Ec(P)$ \. as
$$f\partial(x) =
\begin{cases} \ f(t_{i+1})-1 & \ \ \text{ if \ }x=t_i\text{ \, for some } \, i<r\hskip.03cm, \\
\ n &  \ \ \text{ if \ $x=t_r$}\hskip.03cm,\\
\ f(x)-1\hskip.03cm &  \ \ \ \text{otherwise} .
\end{cases}
$$
We think of~$\partial$ as an operator applied on the right, and write \. $\partial: \hskip.03cm f \hskip.03cm\to\hskip.03cm f\hskip.03cm \partial$.

An \defn{evacuation} \. $\varepsilon: \Ec(P) \to \Ec(P)$  \. is a another operator
on linear extensions defined as follows.   Denote by \hskip.03cm $\partial_i$ \hskip.03cm
as the promotion on a poset obtained by restriction to elements with values \.
$1,\ldots,i$, so that \hskip.03cm $\partial_n=\partial$ \hskip.03cm and \hskip.03cm $\partial_1=1$. Then \hskip.03cm $\varepsilon$ \hskip.03cm is defined
as the composition \. $\varepsilon := \hskip.03cm\partial_n \hskip.03cm \circ \hskip.03cm\dots\hskip.03cm\circ\hskip.03cm\partial_1$\hskip.03cm,
and we write \. $f\varepsilon = f\hskip.03cm\partial_n \hskip.03cm \cdots\hskip.03cm\partial_1$\hskip.03cm.

\smallskip

The promotion and evacuation maps can be interpreted using group actions on linear extensions as follows.

\smallskip

Let \hskip.03cm $\textrm{G}_n=\<\tau_1,\ldots,\tau_{n-1}\>$ \hskip.03cm be an infinite Coxeter group with the relations
\begin{equation}\label{eq:Coxeter}
\tau_1^2\. = \. \ldots \. = \tau_{n-1}^2 \. = \. 1 \qquad \text{and} \qquad \tau_i\hskip.03cm\tau_j\. = \. \tau_j\hskip.03cm \tau_i
\ \ \text{ for all } \ \, |i-j|\. > \.1\hskip.03cm.
\end{equation}
Note that the symmetric group \hskip.03cm $S_n$ \hskip.03cm is a quotient of~$\hskip.03cm\textrm{G}_n$.
We also define elements \. $\delta_2,\ldots,\delta_{n}=\delta\in \textrm{G}_n$ \. as follows:
$$\delta_k \. := \. \tau_1 \hskip.03cm \tau_2 \.\cdots \.\tau_{k-1} \ \ \. \text{for} \ \ 1< k \le n\.,
\quad \text{and} \quad \gamma \. := \. \delta_n \hskip.03cm \delta_{n-1} \hskip.03cm \cdots \hskip.03cm \delta_2 \hskip.03cm.
$$
Note that \. $\textrm{G}_n=\<\delta_2,\ldots,\delta_n\>$ and that $\gamma$ is an involution, $\gamma^2=1$,


With every linear extension \hskip.03cm $f\in \Ec(P)$ \hskip.03cm we associate a  word \. $\textbf{\textit{x}}_f \hskip.03cm=\hskip.03cm x_1\ldots x_n\hskip.03cm \in X^\ast$,
such that \. $f(x_i) =i$ \. for all \. $1\le i \le n$.  In the notation of the previous section, this says
that \. $X=\{x_1,\ldots,x_n\}$ \. is a natural labeling corresponding to~$f$.

We can now define the action of \hskip.03cm $\textrm{G}_n$ \hskip.03cm on \hskip.03cm $\Ec(P)$ \hskip.03cm as the right
action on the words \hskip.03cm $\textbf{\textit{x}}_f$, \hskip.03cm $f\in \Ec(P)$.  For \. $\textbf{\textit{x}}_f \hskip.03cm =\hskip.03cm x_1\ldots \hskip.03cm x_n$ \. as above, let
\begin{equation}\label{eq:tau-def}
(x_1\ldots \hskip.03cm x_n) \. \tau_i \ := \ \begin{cases} \ x_1 \ldots \hskip.03cm x_n, & \ \text{if \, $x_i \prec x_{i+1}$}\hskip.03cm,\\
\ x_1\dots x_{i+1} \hskip.03cm x_i \dots x_n\hskip.03cm, & \ \text{if \, $x_i \parallel x_{i+1}$}\hskip.03cm.
\end{cases}
\end{equation}


Observe that if \. $1= i_1 < i_2 <\dots <i_r\le n$ \. are the indices of the lexicographically smallest maximal chain in the linear extension~$f$, then
$$
(\textbf{\textit{x}}_f) \. \delta \, = \, (x_1\ldots \hskip.03cm x_n) \. \delta \, = \, x_2 \ldots \hskip.03cm x_{i_2-1} \hskip.03cm x_{i_1}
\ldots \hskip.03cm x_{i_r-1} \hskip.03cm x_{i_{r-1}} \ldots \hskip.03cm x_{i_r} \, = \, \textbf{\textit{x}}_{f\partial}\.,
$$
where \hskip.03cm $\delta=\delta_n$ \hskip.03cm as above and $\textbf{\textit{x}}_f \delta = \textbf{\textit{x}}_{f\partial}$ is the promotion operator.

\smallskip

\begin{prop}[{\rm see e.g.~\cite[Prop.~4.1]{AKS}}{}]
\label{p:LE-transitive}
Let \. $P=(X,\prec)$ \. be a poset on with \. $|X|=n$ \. elements.
Then group \. {\rm $\textrm{G}_n$} \hskip.03cm acts transitively on \hskip.03cm $\Ec(P)$.
\end{prop}

\smallskip

\begin{rem}
The proposition is a folklore result repeatedly rediscovered in
different contexts.  For the early proofs and connections to Markov chains,
see~\cite{KK,Mat}.  For a brief overview of generalizations and further
references, we refer to the discussion which follows Prop.~1.2
in~\cite{DK1}.
\end{rem}

\smallskip

\subsection{Generalization to restricted posets}\label{ss:restricted-gen}
Let \hskip.03cm $P=(X,\prec)$.  Fix a sequence of $k$ elements \. $\textbf{\textit{u}}=(u_1,\ldots,u_k) \in X$ \.
and a sequence of $k$ distinct integers \. $\textbf{{\textit{a}}} = (a_1,\ldots,a_k)$, such that \.
$1\leq a_1 < \ldots < a_k \leq n$.  A \defn{restricted linear extension}
with respect to \hskip.03cm $(\textbf{\textit{u}},\textbf{{\textit{a}}})$ \hskip.03cm is a linear extension \hskip.03cm $f\in \Ec(P)$ \hskip.03cm
 such that \. $f(u_i)=a_i$ \. for all \. $1\le i\le k$. As in the introduction, we
 denote this set by \. $\Ec(P,\hskip.03cm\textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})$.

Our first goal is to modify and generalize Proposition~\ref{p:LE-transitive} for
restricted linear extensions.
For simplicity assume that \. $a_i +1 < a_{i+1}$ \. for all \. $1\le i< k$.
Otherwise, we can identify elements \hskip.03cm $u_i\sim u_{i+1}$ \hskip.03cm and consider
the equivalent problem for the so obtained smaller poset. We also assume $a_1>1$ and $a_k<n$, since otherwise the corresponding element $u_1$ or $u_n$ should be minimal/maximal and can be removed from the poset, again reducing the problem.
We also assume that $u_i \prec u_{i+1}$ in the poset.


\smallskip

Let \. $A:=\{a_1,\ldots, a_k\}$ \. and \. $A'=\{a_1-1,\ldots, a_k-1\}$, so \. $A\cap A'=\varnothing$ \.
by the assumption.
Let
$$
\textrm{H}_n(\textbf{{\textit{a}}}) \, = \, \<\hskip.03cm\tau_i, \. \sigma_r \ : \ 1\le i < n, \. i\notin A \cup A', \. 1\le r\le k\hskip.03cm\>
$$
be an infinite group
with relations as in~\eqref{eq:Coxeter} and \. $\sigma_r^2=1$ \. for all \. $1\le r \le k$.
This is a free product of several infinite Coxeter groups which acts on \hskip.03cm $\Ec(P, \hskip.03cm \textbf{\textit{u}},\hskip.03cm \textbf{{\textit{a}}})$ \hskip.03cm
as follows.

First, for all \. $i\notin A \cup A'$, \. $1\le i < n$, the action of \hskip.03cm $\tau_i$ \hskip.03cm
defined in~\eqref{eq:tau-def} can be restricted  to act on \hskip.03cm $\Ec(P, \hskip.03cm \textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})$.
Next, for all \. $1\le r \le k$ \. and \. $j=a_i$ \. define the action
of~$\hskip.03cm \sigma_i$ \hskip.03cm on \hskip.03cm $\Ec(P,\hskip.03cm \textbf{\textit{u}},\textbf{{\textit{a}}})$:
$$
(x_1\ldots \hskip.03cm x_n) \. \sigma_i \ := \ \begin{cases}  \ x_1 \ldots \hskip.03cm x_{j+1} \hskip.03cm x_j \hskip.03cm x_{j-1} \ldots \hskip.03cm x_n &
\ \text{if } \ \ x_{j-1} \parallel  x_j\., \ \. x_{j-1} \parallel x_{j+1} \ \ \text{and} \ \, x_{j}  \parallel  x_{j+1}\,,\\ \
x_1\ldots \hskip.03cm x_{j-1} \hskip.03cm x_j \hskip.03cm x_{j+1} \ldots \hskip.03cm x_n & \text{otherwise}\hskip.03cm.
\end{cases}
$$
Here we continue using our convention of association of \hskip.03cm $\textbf{\textit{x}}_f$ \hskip.03cm with \. $f \in \Ec(P,\hskip.03cm \textbf{\textit{u}},\textbf{{\textit{a}}})$.

Note that when \. $x_{j-1}  \parallel  x_j$ \. and \. $x_{j}  \parallel  x_{j+1}$ \. we have
 $$
 \textbf{\textit{x}} \. \sigma_i \, = \textbf{\textit{x}} \. \tau_j \hskip.03cm \tau_{j-1} \hskip.03cm \tau_j \, = \, \textbf{\textit{x}} \. \tau_{j-1}\hskip.03cm \tau_j\hskip.03cm \tau_{j-1}\hskip.03cm.
 $$
However, when \. $x_{j-1} \prec x_{j}$ \. and \. $x_j  \parallel  x_{j+1}$ \. we have \. $\textbf{\textit{x}} \. \sigma_i \. = \. \textbf{\textit{x}}$, but
$$\textbf{\textit{x}} \. \tau_{j-1} \hskip.03cm\tau_j\hskip.03cm \tau_{j-1} \, \neq  \, \textbf{\textit{x}},
$$
since \. $x_j$ \hskip.03cm has been moved to $(j+1)$-st position. The same property holds when
 \. $x_{j-1} \parallel  x_{j}$ \. and \. $x_j \prec x_{j+1}$\hskip.03cm.

\smallskip

\begin{ex}\label{e:group-H-not}
Let us note that the action of \hskip.03cm $\textrm{H}_n(\textbf{{\textit{a}}})$ \hskip.03cm on \hskip.03cm $\Ec(P, \hskip.03cm\textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})$ \hskip.03cm
is not necessarily transitive. For example, let \hskip.03cm $P=\bigl(X,\prec)$, where
\. $X=\{x,y,u_1,z,u_2\}$, be a poset isomorphic to \. $C_3 + C_1 + C_1$ \. with \.
$u_1 \prec z \prec u_2$ \. and $x,y$ incomparable to \. $\{u_1,z,u_2\}$.
Now, when \. $a_1=2$ \. and \. $a_2=4$, the action of group $\textrm{H}_5(\textbf{{\textit{a}}})$ \. has two orbits:
\. $\{xu_1zu_2y\}$ \. and \. $\{yu_1zu_2x\}$.  This shows that to generalize
Proposition~\ref{p:LE-transitive} we need to enlarge group~$\textrm{H}_5(\textbf{{\textit{a}}})$.
\end{ex}

\smallskip

Let \. $\wh{\textrm{G}}_n=\bigl\<\tau_{i\hskip.03cm j} \.:\. 1\leq i<j\leq n\bigr\>$ \. be an infinite group
with relations
\begin{equation}\label{eq:tau-G-def}
\aligned
 \tau_{i\hskip.03cm j}^2 \. = \. 1  & \qquad \text{for all } \ \ 1\le i<j\le n\hskip.03cm, \\
 \tau_{i\hskip.03cm j} \. \tau_{k\hskip.03cm \ell} \. = \. \tau_{k\hskip.03cm  \ell} \.\tau_{i\hskip.03cm j} & \qquad \text{for all } \ \ 1\le i<k<\ell<j\le n\hskip.03cm.
\endaligned
\end{equation}
Define the action of \. $\wh{\textrm{G}}_n$ \hskip.03cm on \hskip.03cm $\Ec(P)$ \hskip.03cm as
$$(x_1\ldots \hskip.03cm x_n) \. \tau_{i\hskip.03cm j} \ := \ \begin{cases}
\ x_1\ldots \hskip.03cm x_j \ldots \hskip.03cm x_i \ldots x_n & \
\text{if \. $x_i \parallel y$ \. and \. $x_j \parallel y$ \. for all \. $y \in\{x_{i+1},\ldots,x_{j-1}\}$}, \\
\ x_1 \ldots \hskip.03cm x_n & \ \text{otherwise}.
\end{cases}
$$
In the notation above, we have \. $\tau_{i \. i+1} = \tau_i$\., so \. $\textrm{G}_n \subset \wh{\textrm{G}}_n$ \. is a subgroup.
For brevity, we write \hskip.03cm $\tau_i$ \hskip.03cm for \hskip.03cm $\tau_{i \. i+1}$ \hskip.03cm from this point on.

Finally, let \. $\wh{\textrm{G}}_n(\textbf{{\textit{a}}})$ \. be a subgroup of \hskip.03cm $\wh{\textrm{G}}$ \hskip.03cm defined as follows:
$$\wh{\textrm{G}}_n(\textbf{{\textit{a}}}) \, := \, \bigl\<\hskip.03cm \tau_{i\hskip.03cm j} \, : \, i,j\notin A, \,  1\le i<j\le n \hskip.03cm\bigr\>\hskip.03cm.
$$

\smallskip

\begin{thm}\label{t:LE-gen-transitive}
Let \. $P=(X,\prec)$ \. be a poset  with \. $|X|=n$ \. elements.
Fix a chain of $k$ elements \. $\textbf{\textit{u}}=(u_1,\ldots,u_k) \in X$ \.
and an increasing sequence of $k$ distinct integers \. $\textbf{{\textit{a}}} = (a_1,\ldots,a_k)$.
Then group \. {\rm $\wh{\textrm{G}}_n(\textbf{{\textit{a}}})$} \hskip.03cm defined above
acts transitively on \hskip.03cm $\Ec(P, \hskip.03cm \textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})$.
\end{thm}

\begin{proof}
Suppose \. $\Ec(P,\hskip.03cm \textbf{\textit{u}},\hskip.03cm \textbf{{\textit{a}}}) \neq \varnothing$. Fix \. $f \in \Ec(P,\hskip.03cm \textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})$ \. and write \.
$\textbf{\textit{x}}_0=x_1\ldots x_n$ \. corresponding to the natural labeling \. $f(x_i)=i$.  For every \.
\. $\textbf{\textit{y}} = y_1\ldots y_n$ \. corresponding to a linear extension \. $g \in \Ec(P,\hskip.03cm \textbf{\textit{u}},\hskip.03cm \textbf{{\textit{a}}})$,
let \hskip.03cm $\operatorname{{\rm inv}}(\textbf{\textit{y}})$ \hskip.03cm be the number of inversions in the permutation~$f(\textbf{\textit{y}}):=\bigl(f(y_1),\ldots,f(y_n)\bigr)$.  We claim that
unless \. $\textbf{\textit{y}}=\textbf{\textit{x}}_0$, we can use operators in \. $\wh{\textrm{G}}_n(\textbf{{\textit{a}}})$ \. to decrease \hskip.03cm $\operatorname{{\rm inv}}(\textbf{\textit{y}})$.
Using this recursively, we can then reach \hskip.03cm $\textbf{\textit{x}}_0$ \hskip.03cm as the unique element for which~$\hskip.03cm \operatorname{{\rm inv}}(\textbf{\textit{x}}_0) =0$.

Consider the permutation \. $w:=\bigl(f(y_1),\ldots,f(y_n)\bigr)$.  If \. $w\ne \mathbf{1}$,
there exist elements \. $f(y_i), f(y_{i+1}) \in w$ \. such that \. $f(y_i)>f(y_{i+1})$.
Then we have \. $y_i  \parallel  y_{i+1}$.  We call such \. $(y_i, y_{i+1})$ \. a \defn{descending pair}.
Suppose there is a descending pair with \. $y_i, y_{i+1} \not \in \textbf{\textit{u}}$.
Then \. $\tau_i \in \textrm{H}_n(\textbf{{\textit{a}}})$, and \. $\textbf{\textit{y}}\. \tau_i \hskip.03cm = \hskip.03cm \ldots y_{i+1}\hskip.03cm y_i\ldots$ \hskip.03cm
Therefore, we have \. $\operatorname{{\rm inv}}(\textbf{\textit{y}}\hskip.03cm\tau_i)\hskip.03cm =\hskip.03cm \operatorname{{\rm inv}}(\textbf{\textit{y}}) -1$, which proves the claim in this case.

In the remaining cases, every descending pair involves at least one element from~$\textbf{\textit{u}}$,
which are fixed points of the labeling~$f$.  Suppose there are two adjacent descending pairs, i.e.\
\. $f(y_{i-1})>f(y_i)>f(y_{i-1})$ \. and \. $y_i \in \textbf{\textit{u}}$. Then we have \.
$\operatorname{{\rm inv}}(\textbf{\textit{y}}\tau_{i-1 \. i+1})=\operatorname{{\rm inv}}(\textbf{\textit{y}})-3$, which prove the claim in this case.

Finally, suppose every descending pair involves at least one element from~$\textbf{\textit{u}}$, and none are adjacent.
Let  \hskip.03cm $i_1-1$ \hskip.03cm be the last descent of $w$. Then \hskip.03cm $i_1-1\in \textbf{{\textit{a}}}$, i.e. $i_1-1=a_t$ \. for some $a_t\in \textbf{{\textit{a}}}$,
and we have \.
$a_t=w_{a_t} >w_{i_1}$.  To see this, suppose the contrary that the last descent in $w$ is at $i_1 -1 =a_t-1$, so $w_{i_1-1} > w_{a_t}=a_t$ and all elements of $w$ after $a_t$ are increasing. Since $a_t$ is a fixed point and we have $n-a_t$ positions after $a_t$ filled with numbers larger than $a_t$, i.e. from the interval $\{a_t+1,\ldots,n\}$, we must have $w_i=i$ for $i=a_t,\ldots,n$, so all values $>a_t$ appear after it. Thus $w_{a_t-1}<a_t =w_{a_t}$, reaching a contradiction, and so the last descent is at $a_t$.


Let \. $m <i_1-1$ \. be the largest value for which \. $w_{m}>i_1-1=a_t$. Such value exists
since by the reasoning above at least one of \. $\{i_1,\ldots,n\}$ \. appears before~$i_1-1$.  Now,
form a sequence \. $i_1\hskip.03cm>\hskip.03cm i_2\hskip.03cm>\hskip.03cm\ldots\hskip.03cm>\hskip.03cm i_r\hskip.03cm >\hskip.03cm i_0= m$\hskip.03cm, such that \hskip.03cm
$i_j$ \hskip.03cm is the largest index smaller than \hskip.03cm $i_{j-1}$ \hskip.03cm  such that \. $w_{i_j}<w_{i_{j-1}}$.
Note that by similar interval arguments we must have that \. $f(y_{i_j})<i_j$ \.
and they do not hit any of the elements in~$\textbf{{\textit{a}}}$.  Note that these indices give a maximal
increasing subsequence in~$w_{m+1}\ldots w_n$ which ends at~$w_{i_1}$.

Now apply \. $\tau_{m\. i_r}\. \tau_{i_r \. i_{r-1}} \. \cdots \. \tau_{i_2\. i_1}$, which is nontrivial as it transposes the element $y_m$, incomparable to all elements in positions $\in [m+1,i_1]$, with the elements $y_{i_r},\ldots$ which are also incomparable with the elements in the corresponding interval.
Note that this is the cycle permutation \. $(m,i_1,i_2,\ldots)$ \. so that $y_{m}$ moves to position $i_1$,
and the other elements slide down. This give a linear extension where the elements sliding to left bypass
only elements of larger value of~$f$, and hence respect the partial order.  Since \hskip.03cm $f(y_{m})$ \. is
larger than the elements it jumps over, the resulting permutation has fewer inversions.  This proves the claim
in that case and completes the proof of the theorem.
\end{proof}

\smallskip

\subsection{Vanishing conditions}\label{ss:restricted-vanish}
For \. $\textbf{{\textit{a}}}=(a_1,\ldots,a_k)$, let \. $\textbf{{\textit{a}}}^{\<i\>} := (a_1,\ldots,a_i+1,\ldots,a_k)$.
By definition, the operator
$$
\tau_{a_i}\, : \ \Ec(P,\textbf{\textit{u}}, \textbf{{\textit{a}}}) \cup \Ec\bigl(P,\textbf{\textit{u}},\textbf{{\textit{a}}}^{\<i\>}\bigr) \ \to \
\Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}}) \cup \Ec\bigl(P,\textbf{\textit{u}},\textbf{{\textit{a}}}^{\<i\>}\bigr)
$$
is an involution. For \. $i< j$, let
$$\delta_{i \hskip.03cm j} \, := \, \tau_i \. \tau_{i+1} \. \cdots \. \tau_{j-1} \quad \text{and} \quad
\delta_{j\hskip.03cm i} \, := \, \tau_{j-1} \. \cdots \. \tau_{i+1} \. \tau_i
$$
be the \defn{promotion operator} starting at position~$i$ and ending in position~$j$, and
the \defn{demotion operator} starting at position~$j$ and ending in position~$i$.

\smallskip

\begin{proof}[Proof of Theorem~\ref{t:vanish}]
Without loss of generality, we can assume that poset \. $P=(X,\prec)$ \.
has a unique minimal element~$\widehat{0}$ and unique maximal element~$\widehat{1}$.
Since \. $f\big(\widehat{0}\big) = 1$ \. and \. $f\big(\widehat{1}\big) = n$ \. for
every linear extension \. $f\in \Ec(P)$, we can also add \. $u_0 = \widehat{0}$ \.
and \. $u_{k+1} = \widehat{1}$ \. to the chain \.
$u_1\prec \ldots \prec u_k$\hskip.03cm, and set \. $a_0=1$, \. $a_{k+1}=n$.
Equation~\eqref{eq:Sta-gen-vanish} then simplifies to
\begin{align}\label{eq:a_conditions}
a_j\. - \. a_i \ > \ h(u_i,u_j) \ \quad \text{ for all } \quad 0\leq i<j \leq k+1.
\end{align}


First, let us show  that inequalities~\eqref{eq:a_conditions} always hold.
Indeed, in every word \hskip.03cm $\textbf{\textit{x}}_f$ \hskip.03cm
corresponding to a linear extension \. $f\in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$ \. with \. $f(u_i)=a_i$\hskip.03cm,
we must have the elements from \. $\bigl(u_i,u_j\bigr)_P$ \. lie between~$u_i$ and~$u_j$,
and hence \. $a_j-a_i>h(u_i,u_j)$.

\smallskip

In the opposite direction, assume that the inequalities~\eqref{eq:a_conditions} hold
for all \. $0\leq i<j \leq k+1$.  To prove that \. $\Ec(P,\textbf{\textit{u}},\hskip.03cm\textbf{{\textit{a}}})\ne \varnothing$,
proceed by induction on~$k$.
For \hskip.03cm $k=1$, let \hskip.03cm $\alpha$ \hskip.03cm be a word obtained from totally ordering of the poset
interval \. $\big(\widehat{0},u_1\big)$, and \hskip.03cm $\beta$ \hskip.03cm be a word obtained from totally ordering
of the poset interval \. $\big(u_1,\widehat{1}\big)$. Order the remaining elements of \hskip.03cm
$P-u_1$ \hskip.03cm into a word~$\gamma$, and then insert \hskip.03cm $u_1$ \hskip.03cm at position \hskip.03cm $a_1$ \hskip.03cm in the
concatenation \. $\alpha\hskip.03cm\gamma\hskip.03cm\beta$. Since \hskip.03cm $u_1 \parallel \gamma$, \. $a_1>|\alpha|$, and \. $n-a_1>|\beta|$,
this is a linear extension in \hskip.03cm $\Ec(P,u_1,a_1)$.


Suppose now that the result holds for all sequences of length \. $k\ge 1$,
and let \. $\textbf{\textit{y}} \in \Ec(P,\hskip.03cm \textbf{\textit{u}},\hskip.03cm \textbf{{\textit{a}}})$. Now let \hskip.03cm $u_{k+1}$ \hskip.03cm
be another element and \hskip.03cm $a_{k+1}$ \hskip.03cm satisfy the conditions
in the statement. Suppose that the position of \hskip.03cm $u_{k+1}$ \hskip.03cm is at \. $a'\neq a_{k+1}$.
Let us show that if \hskip.03cm $a'<a_{k+1}$, then we can move \hskip.03cm $u_{k+1}$ \hskip.03cm to position \hskip.03cm $a'+1$
without moving the other~$u$'s, and if \hskip.03cm $a'>a_{k+1}$ we can move \hskip.03cm $u_{k+1}$ \hskip.03cm one position down.
Repeating this we will eventually get \hskip.03cm $u_{k+1}$ \hskip.03cm at a position \hskip.03cm $a'=a_{k+1}$, to obtain
the desired linear extension.

\smallskip

From now on we act with the group $G$, and the promotion and demotion operators $\delta_{ij}$ to transform $\textbf{\textit{y}}$.

Let \. $a'<a_{k+1}$. Since \. $n-a'>n-a_{k+1}\geq h(u_{k+1},\widehat{1})$, there must be at least
one element in~$\textbf{\textit{y}}$ appearing after \hskip.03cm $u_{k+1}$ \hskip.03cm which is incomparable to \hskip.03cm $u_{k+1}$; denote by \hskip.03cm $z$ \hskip.03cm the first such element, at position $t$. Then the elements between \hskip.03cm $u_{k+1}$ \hskip.03cm and \hskip.03cm $z$ \hskip.03cm are incomparable with $z$, since they must be $\succ u_{k+1}$. Inserting~{\hskip.03cm $z$} \hskip.03cm immediately before \hskip.03cm $u_{k+1}$ \hskip.03cm, i.e.\ forming the word \hskip.03cm $\textbf{\textit{y}}\delta_{t a'}$, then respects the partial order and shifts \hskip.03cm $u_{k+1}$ \hskip.03cm to position~$\hskip.03cm a'+1$.
Note that this transformation does not move $u_1,\ldots, u_k$ since we assume that $u_k \prec u_{k+1}$, which implies that $a_k <a$.

Suppose now that \. $a'>a_{k+1}$. Then \. $a'> h(\widehat{0},u_{k+1}) +1$, so there is an element before \hskip.03cm $u_{k+1}$ \hskip.03cm
which is incomparable to \hskip.03cm $u_{k+1}$. Let \hskip.03cm $z_0$ \hskip.03cm be the last such element, and suppose that it is at position \. $i_0\in (a_{r-1},a_{r})$. Note that the elements between \hskip.03cm $z_0$ \hskip.03cm and \hskip.03cm $u_{k+1}$ in~$\textbf{\textit{y}}$ must be incomparable to~{\hskip.03cm $z_0$}, since by minimality they must be all~{\hskip.03cm$\prec u_{k+1}$}. If $z_0$ appears after~$\hskip.03cm u_k$, then we obtain $\textbf{\textit{y}}\delta_{i_0a'}$, where $z$ is inserted  after \hskip.03cm $u_{k+1}$ \hskip.03cm and  \hskip.03cm $u_{k+1}$ shifts to position \hskip.03cm $a'-1$.  Otherwise, since \. $a'-a_k > h(u_{k+1},u_k)+1$, there is an element \hskip.03cm $z_k$ \hskip.03cm between $u_k$ and $u_{k+1}$ in $\textbf{\textit{y}}$ such that  $z_k$ is incomparable to either $u_k$ or $u_{k+1}$. Since \. $z_k \neq z_0$, we must have \. $z_k  \parallel  u_k$, and let this \hskip.03cm $z_k$ \hskip.03cm be the first such element after \hskip.03cm $u_k$ \hskip.03cm at position~$i_k$.

In general, for every \.$t \in [r,k]$\. we define $z_t$ at position \.$i_t<a'$\. to be the first element after \.$u_t$\., such that \hskip.03cm $z_t \parallel u_t$. Note that such element exists, which is seen as follows. Since  \.$h(u_t,u_{k+1})+1<a'-a_t$\. there is an element \.$z$ \. between \.$u_t$ \. and \. $u_{k+1}$ \. incomparable to at least one of them. However, for all such \.$z\prec u_{k+1}$\., so we must have \.$z \parallel u_t$. Next, observe that \.$z_t$  is incomparable to all elements in $\textbf{\textit{y}}$ appearing between $u_t$ and $z_t$.
Now transform $\textbf{\textit{y}}$ as follows. First, let \hskip.03cm $\textbf{\textit{y}}^0:= \textbf{\textit{y}} \delta_{i_0 \. a'}$, and note that here $z_0$ is sent to position $a'$ and all elements in between have been shifted down one position. Let \hskip.03cm $a'_t:=a_t-1$ \hskip.03cm and \hskip.03cm $i'_t:=i_t-1$ \hskip.03cm be the positions of $u_t$ and $z_t$ in~$\textbf{\textit{y}}^0$. Next, let $\textbf{\textit{y}}^1 = \textbf{\textit{y}}^0 \. \delta_{i'_r \. a_r'}$ which moves $z_r$ before $u_r$, so the position of $u_r$ is restored to $a_r$ as well as all elements between them. Suppose that $i_r \in (a_{p-1}, a_{p})$. Let then $\textbf{\textit{y}}^2:=\textbf{\textit{y}}^1\. \delta_{i'_p \. a'_p}$, so the element $z_p$ is demoted to the position before $u_p$, and thus all other elements at positions $[a_p,\.i_p]$ have now restored their original position from~$\textbf{\textit{y}}$. Continuing this way, if \. $i_p \in (a_{q-1},\.a_q)$\. we obtain $\textbf{\textit{y}}^3:= \textbf{\textit{y}}^2\. \delta_{i'_q\. a'_q}$ and so on until we have shifted
all elements \hskip.03cm $u_r,\ldots,u_k$ \hskip.03cm to their positions \hskip.03cm $a_r,\ldots,a_k$. Also, \hskip.03cm $u_{k+1}$ \hskip.03cm is at position~$a'-1$, which is what we needed to show. This completes the proof.
\end{proof}

\smallskip

\begin{proof}[Proof of Corollary~\ref{cor:Sta-gen-vanish-poly}]
The first part follows trivially from~\eqref{eq:Sta-gen-vanish} or, equivalently,
its simplified version~\eqref{eq:a_conditions}.  For the second part, note that the proof above is
completely constructive and builds \. $f\in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$ \. in polynomial time starting with
a linear extension \. $g\in \Ec(P)$.  The details are straightforward.
\end{proof}


\smallskip

\subsection{Uniqueness conditions}\label{ss:restricted-unique}

In the next lemma, we show that, given a linear extension \hskip.03cm $f \in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$,
we can check if such~$f$ is unique in polynomial time.

In the notation of  Theorem~\ref{t:vanish},
let \. $v_i:=f^{-1}(a_i-1)$ \. and \. $w_i:=f^{-1}(a_i+1)$ \.
for \. $1\le i \le k$.
We adopt the convention that \hskip.03cm $v_1=\widehat{0}$ \hskip.03cm if \hskip.03cm $a_1=1$,
and \hskip.03cm $w_k=\widehat{1}$ \hskip.03cm if \hskip.03cm $a_k=n$.  For \. $1 \leq i \leq  j \leq n$,
let
\[ f^{-1}[i,j] \ := \ \bigl\{\hskip.03cm f^{-1}(i)\., \.\ldots \.,  f^{-1}(j)\hskip.03cm  \bigr\}.
\]

\smallskip


\begin{thm}\label{t:gen-Stanley-unique}
In the notation of Theorem~\ref{t:vanish}, let \. $f \in \Ec(P,\textbf{{\textit{a}}},\textbf{\textit{u}})$ \.
be a linear extension as in the theorem.
Then \hskip.03cm $|\Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})|=1$ \, \underline{if and only if} \,
	the following conditions hold:
	\begin{equation*
\aligned
		& (1) \quad \text{$f^{-1}[a_i+1,a_{i+1}-1]$ \. forms a chain in $P$  for every \. $1\le i \le k$, \hskip.03cm and } \\
	& (2) \quad  \text{There are no \. $1 \leq i \leq j \leq k$\hskip.03cm, \. such that \. $\{v_i,w_j\} \hskip.03cm \parallel \hskip.03cm f^{-1}[a_i,a_j]$.}	
\endaligned
\end{equation*}
\end{thm}


\begin{proof}
For the \hskip.03cm $\Rightarrow$ \hskip.03cm direction, note that~$(1)$ follows directly. Indeed,
recall that \. $e(P)>1$ \.  unless \hskip.03cm $P$ \hskip.03cm is a chain.  Therefore if the restriction of \hskip.03cm $P$ to
\. $\big\{f^{-1}(a_i+1),\ldots,f^{-1}(a_{i+1}-1)\big\}$ \. is not a chain, then there is more than one
linear extension over these elements, which extends to the desired linear extension \. $g\in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$, \. $g\ne f$.
For~$(2)$, suppose to the contrary that \. $v_i,w_j \hskip.03cm \parallel \hskip.03cm f^{-1}[a_i,a_j]$.
Then swapping the value of \hskip.03cm $f(v_i)$ \hskip.03cm and $f(w_j)$ \hskip.03cm via $\textbf{\textit{x}}_f \tau_{a_i-1 \hskip.03cm a_j+1}$ we  get a new linear extension,
a contradiction.
	
\smallskip

For the \hskip.03cm $\Leftarrow$ \hskip.03cm direction, suppose that~(1) and~(2) hold and there exists \hskip.03cm $g\in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$ \hskip.03cm
for some \hskip.03cm $g\ne f$. By Theorem~\ref{t:LE-gen-transitive} we have that there is an element \hskip.03cm $\pi \in \wh{\textrm{G}}_n(\textbf{{\textit{a}}})$, s.t. $\textbf{\textit{x}}_f \pi = \textbf{\textit{x}}_g$. Write $\pi$ as the minimal (reduced) product of transpositions $\pi = \tau_{r_1 \hskip.03cm s_1} \cdots$ which act nontrivially. So $\textbf{\textit{x}}_f \tau_{r_1 \hskip.03cm s_1} \neq \textbf{\textit{x}}_f$ and thus $\{f^{-1}(r_1), f^{-1}(s_1)\} \hskip.03cm \parallel \hskip.03cm f^{-1}[r_1+1,s_1-1]$. Since the elements
in \hskip.03cm  $f^{-1}[a_i+1,a_{i+1}-1]$ \hskip.03cm form a chain we must have that $r_1 =a_i-1$ for some $i$ and that $s_1 = a_j+1$ for some $j$. Note that by definition \hskip.03cm $r_1<s_1$ \hskip.03cm and \hskip.03cm $r_1,s_1 \not\in \textbf{{\textit{a}}}$. Thus \. $\{ f^{-1}(a_i-1), f^{-1}(a_j+1)\} \parallel f^{-1}[a_i,a_j]$, and so condition~(2) does not hold, a contradiction.
\end{proof}





\smallskip

\begin{proof}[Proof of Corollary~\ref{cor:Sta-gen-uniqueness-poly}]
By the first part of Corollary~\ref{cor:Sta-gen-vanish-poly}, we can decide if
\. $|\Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})|>0$ \. in polynomial time.  By the second part of the same
corollary, we can find a linear extension \. $f\in \Ec(P,\textbf{\textit{u}},\textbf{{\textit{a}}})$ \. in polynomial
time.  By Theorem~\ref{t:gen-Stanley-unique}, we can decide if such~$f$ is unique
in polynomial time.
\end{proof}

\medskip

\section{Injective proof of the Sidorenko inequality} \label{s:sid}


\subsection{Preliminaries} \label{ss:sid-pre}

Let $P=(X,\prec)$ be a poset with $|X|=n$ elements.  Denote by \hskip.03cm $P|_J$ \hskip.03cm the
restriction of \hskip.03cm $P$ \hskip.03cm to a subset \hskip.03cm $J\subset X$.  We write \hskip.03cm $P-y$ \hskip.03cm
to denote the restriction \hskip.03cm $P|_{X-y}$.
Denote by  \. $P^\ast=(X,\prec^\ast)$ \. the \defn{reverse poset}~:
$$x\prec^\ast y \quad \Longleftrightarrow \quad y \prec x\,, \quad \text{for all} \ \ x, \hskip.03cm y \in X.
$$
Clearly, \hskip.03cm $e(P^\ast)=e(P)$.

Denote by \hskip.03cm $\mathcal C(P)$ \hskip.03cm the set of chains, and by $\mathcal A(P)$ the set of
antichains in~$P$.   The \defn{comparability graph} \hskip.03cm $ {\text {\rm Com} } (P)=(X,E)$ \hskip.03cm
is defined by \. $E=\bigl\{(x,y)~:~x\prec y, \. \text{ where } \. x,y\in X\bigr\}$. Note that
the chains in~$P$ are \emph{cliques} (complete subgraphs) in $ {\text {\rm Com} } (P)$.
Similarly, the antichains in~$P$ are \emph{stable} (independent) \emph{sets} in $ {\text {\rm Com} } (P)$.

Throughout this section, we think of the \defng{promotion} in a different way,
as a map from linear extensions to chains in the poset.
Formally, for $f\in \mathcal E(P)$, let \. $x_1=f^{-1}(1)$. For \hskip.03cm $i>1$, let $x_{i}\in X$ be
an element with the smallest value of~$f$ on \. $\{y~:~x_{i-1}\prec y\}$.
This gives a \defn{promotion chain} \. $C= \bigl[x_1\to x_2\to\ldots \to x_\ell\bigr]\in \mathcal C(P)$, which
can also be viewed as the \emph{DFS path} in the  \emph{Hasse diagram} of~$P$.
Denote by \. $\Phi: \mathcal E(P)\to \mathcal C(P)$ \. the map \. $\Phi(f) = C$.

\bigskip


\begin{lemma}  \label{lem:DFS}
For all $P=(X,\prec)$  and $y\in X$ we have:
$$e(P-y) \. = \. \bigl|\bigl\{g\in \mathcal E(P)\,:\, y \in \Phi(g)\bigr\}\bigr|
$$
\end{lemma}


\medskip

\begin{proof}
Consider a bijection
$$\varphi: \,
\mathcal E(P-y)
\.  \longrightarrow  \.
\bigl\{g\in \mathcal E(P)\,:\,y \in \Phi(f)\bigr\}
$$
defined as follows.  Let \. $f\in \mathcal E(P-y)$, and let
\. $[y\to x_1 \to \ldots \to x_k]$ \. be the
promotion path in the upper order ideal \. $B(y) = \{x\in X\.:\. x \succ y\}$.
Define \. $g=\varphi(f) \in \mathcal E(P)$ \. as follows.  Let \. $g(y):=f(x_1)$, \.
$g(x_i):=f(x_{i+1})$ \. for \. $1\le i < k$, and \. $g(x_k):=n$.  Observe
that in \hskip.03cm $P^\ast$ \hskip.03cm we now have \.
$\Phi(f) \. = \. \bigl[x_k\to\ldots \to x_1 \to y \to \ldots \bigr]$.
Reversing the role of \hskip.03cm $P$ \hskip.03cm and \hskip.03cm $P^\ast$ \hskip.03cm implies the result.
\end{proof}

\bigskip


\begin{cor}[{\rm {see~\cite{EHS}}}{}] \label{cor:antichain}
For every antichain $A\in \mathcal A(P)$ we have
\begin{equation}\label{eq:EHS-ineq}
\sum_{y \in A} \. e(P-y) \, \le \, e(P).
\end{equation}
Furthermore, when \hskip.03cm $A\subseteq X$ \hskip.03cm is the set of minimal elements,
the inequality~\eqref{eq:EHS-ineq} is an equality.
\end{cor}

\begin{proof}
Note that for every $C\in \mathcal A(P)$ and $A\in \mathcal A(P)$ we have $|A\cap C|\le 1$.
Thus, we have:
$$\sum_{y \in A} \. e(P-y) \, = \,
\bigl|\bigl\{f\in \mathcal E(P)\,:\,|\Phi(f)\cap A|=1\bigr\}\bigr| \, \le \, |\mathcal E(P)| \, = \, e(P),
$$
which proves~\eqref{eq:EHS-ineq}.  For the second part, note that for every \. $f\in \Ec(P)$,
the promotion path \hskip.03cm $\Phi(f)$ \hskip.03cm starts with the minimal element in~$A$.  This implies
that~\eqref{eq:EHS-ineq} is an equality, as desired.
\end{proof}

\smallskip

\begin{rem}\label{r:comp}
Lemma~\ref{lem:DFS} is implicit in~\cite{EHS}, which only discusses
equality cases (cf.\ Corollary~\ref{cor:antichain}). By~\cite[Thm~4]{Sid},
map~$\Phi$ gives the \emph{linear extension flow} through $ {\text {\rm Com} } (P)$ viewed as
directed network.  Although Sidorenko gives a combinatorial construction
of this flow in~\cite[Rem~1.2]{Sid}, this construction is also inexplicit.

Let us mention that second part of Corollary~\ref{cor:antichain} implies
by induction that \hskip.03cm $e(P)$ \hskip.03cm depends only on the comparability graph $ {\text {\rm Com} } (P)$,
see~\cite{EHS,Sta-promo}.  The same holds for the order polynomial \hskip.03cm $\Omega(P,t)$,
and can be proved using Ehrhart polynomials~\cite{Sta-two},
cf.~$\S$\ref{ss:finrem-Ehrhart}.  Alternatively, this result can be
shown via certain ``turning upside-down'' flips discussed in
\cite[Exc.~3.163]{Sta-EC}.
\end{rem}


\smallskip

\subsection{Sidorenko's inequality} \label{ss:sid-proof}
As in the introduction, let \. $P=(X,\prec)$ \. and \. $Q=(X,\prec')$ \.
be two posets on the same ground set, such that \. $|C\cap C'|\le 1$ \.
for all \. $C\in \mathcal C(P)$ \. and \. $C'\in \mathcal C(Q)$.
Then \. $\mathcal C(P) = \mathcal A(Q)$ \. and $\mathcal A(P) = \mathcal C(Q)$, by definition.

\bigskip

\begin{lemma}[{\rm cf.~\cite[Lemma~10]{Sid}}{}] \label{lem:main}
For all $P$ and $Q$ as above, we have:
$$
\sum_{y\in X} \, e(P-y) \. e(Q-y) \, \le \, e(P) \. e(Q)\hskip.03cm.
$$
\end{lemma}

\smallskip


\begin{proof}  We have:
$$
\aligned
\sum_{y\in X} \. e(P-y) \. e(Q-y) \, & =_{\text{Lem~\ref{lem:DFS}}} \,
\sum_{y\in X} \. e(Q-y) \, \sum_{C\in \mathcal C(P) \ : \ C\ni y} \. |\{f\in \mathcal E(P)\,:\,\Phi(f)=C\}|
\\& = \hskip.95cm
\sum_{C\in \mathcal C(P)} \, \sum_{y\in C} \. e(Q-y) \, \cdot \, |\{f\in \mathcal E(P)\,:\,\Phi(f)=C\}|
\\
& \le_{\text{Cor.~\ref{cor:antichain}}}
\,
\sum_{C\in \mathcal C(P)} \, e(Q) \, \cdot \, |\{f\in \mathcal E(P)\,:\,\Phi(f)=C\bigr\}|
\\
& \le \   e(Q)  \,  \sum_{C\in \mathcal C(P)} \,|\{f\in \mathcal E(P)\,:\,\Phi(f)=C\}| \quad = \
e(P) \. e(Q).
\endaligned
$$
Here in the third line, Cor.~\ref{cor:antichain} applies to poset~$Q$, since every chain in~$P$
is an antichain in~$Q$.
\end{proof}

\smallskip

\begin{proof}[Proof of Theorem~\ref{t:sid}]
The theorem follows from Lemma~\ref{lem:main}, by induction on $n=|X|$.
\end{proof}

\smallskip

\begin{cor}[{\cite[Thm~11]{Sid}}{}]\label{c:sid-equality}
In notation of Theorem~\ref{t:sid}, the inequality~\eqref{eq:sid} is
an equality \. \underline{if and only if} \. $P$ \hskip.03cm
is a \emph{series-parallel poset}.
\end{cor}

\smallskip

The result is well-known and follows easily by tracing back the inequalities in
the proof of Lemma~\ref{lem:main}.  We omit the details.

\smallskip

\begin{proof}[Proof of Theorem~\ref{t:sid-gen}]
We can rewrite the proof of Lemma~\ref{lem:main} as follows:
$$
\aligned
\sum_{y\in X} \. e(P-y) \. e(Q-y)
\ = \ \sum_{f\in \mathcal E(P)} \. \sum_{g\in \mathcal E(Q)} \. \sum_{y\in \Phi(P)\cap \Phi(Q)} \. 1 \
\le \  k \. e(P) \. e(Q).
\endaligned
$$
The result now follows by induction on~$n\ge k$, with the base \hskip.03cm $n=k$ \hskip.03cm trivial.
\end{proof}

\smallskip


\begin{proof}[Proof of Theorem~\ref{t:sid-SP}]
Let \. $\beta: S_n \to \mathcal E(P_\sigma)\times \mathcal E\bigl(P_{\overline{\sigma}}\bigr)$ \. be
the injection defined implicitly by the proof of Theorem~\ref{t:sid} above.
First, observe that \hskip.03cm $\beta$ \hskip.03cm is computable in polynomial time.  Indeed, by
induction, it is a composition of maps \hskip.03cm $\beta_i$ \hskip.03cm each consisting of applying
maps \hskip.03cm $\Phi$ \hskip.03cm to posets
corresponding to partial permutations $\sigma_i:=(\sigma(1),\ldots,\sigma(i))$
and its dual \hskip.03cm $\overline{\sigma_i}$, see the proof of Lemma~\ref{lem:DFS}.

Second, whenever defined, the inverse map \hskip.03cm $\beta^{-1}$ \hskip.03cm can be computed by the proof
of Lemma~\ref{lem:DFS}, since the inverse of \hskip.03cm $\Phi$ \hskip.03cm on~$P$ is a map \hskip.03cm $\Phi$ \hskip.03cm on~$P^\ast$.
On the other hand, at each stage, the decision if the inverse of \hskip.03cm $\beta_i$ \hskip.03cm exists
reduces to a problem whether a given antichain in the \. $Q_i:=P_{\overline{\sigma_i}}$ \. is a \defn{cut},
i.e.\ it intersects every chain in~$Q_i$.  This is a special case of directed graph
connectivity problem, and thus in~${\textsc{P}}$. Putting this together implies that
we can decide in polynomial time if \. $(f,g) \in \beta(S_n)$,
for all \. $f\in \mathcal E(P_\sigma)$ \. and \. $g\in \mathcal E\bigl(P_{\overline{\sigma}}\bigr)$.

In summary, the function \hskip.03cm $\eta(\sigma)$ \hskip.03cm counts the number of pairs of linear
extensions \hskip.03cm $(f,g)$ \hskip.03cm as above, such that \hskip.03cm $(f,g) \notin \beta(S_n)$.
Since the problem whether \hskip.03cm $(f,g) \in \beta(S_n)$ \hskip.03cm can be decided in
polynomial time, this completes the proof.
\end{proof}


\medskip

\section{Final remarks and open problems}\label{s:finrem}


\smallskip

\subsection{Bj\"orner--Wachs inequality}\label{ss:finrem-HP}
In total, we include three proofs of the Bj\"orner--Wachs inequality:
the original injective proof in~$\S$\ref{s:injective}, the probabilistic proof
via Shepp's inequality in~$\S$\ref{s:OP-induction}, and Reiner's proof
via $q$-analogue in~$\S$\ref{s:q-analogue}.  Another proof was given
by Hammett and Pittel in~\cite[Cor.~2]{HP}, who seemed unaware of the
origin of the problem despite having~\cite{BW89} among the references.
Although somewhat lengthy and technical, their proof is completely
self-contained and is based on a geometric probability argument.
It is similar in spirit to Reiner's proof, but without benefits
of the brevity.

\smallskip

\subsection{Order polynomial} \label{ss:finrem-OP}
There is surprisingly little literature on the order polynomials
given that they emerge naturally in both P-partition theory and
discrete geometry.  We refer to~\cite{Joc} for order polynomials in
the case of symmetric posets, which are of independent interest,
and to~\cite{LT} for some computations.

It seems, there are more conjectures and open problems than results
in the subject.  It addition to the Kahn--Saks Conjecture~\ref{conj:KS-mon}
and the Graham Conjecture~\ref{conj:Graham}, we have our own
Conjecture~\ref{conj:KS-FKG}.  We should warn the reader that there seem
to be insufficient effort towards testing of these conjectures, so it would
be interesting to obtain more computational evidence.


\smallskip

\subsection{Ehrhart polynomial}\label{ss:finrem-Ehrhart}
It is a classical observation by Stanley \cite{Sta-two},
that the order polynomial \hskip.03cm $\Omega(P,t+1)$ \hskip.03cm is the
\defng{Ehrhart polynomial} of the corresponding
order polytope \hskip.03cm $\mathcal{O}_P$\hskip.03cm:
$$
\mathrm{Ehr}(\mathcal{O}_P,t) \, = \, \Omega(P,t+1)\hskip.03cm.
$$
This allows one to translate the results from combinatorial
to geometric language ad vice versa.

Notably, our Example~\ref{e:OP-Stanley} is motivated by Stanley's
\hskip.03cm {\tt MathOverflow} \hskip.03cm observation\footnote{Richard P.~Stanley,
\href{https://mathoverflow.net/q/200574}{mathoverflow.net/q/200574}
(March~20, 2015).} that the order
polynomial \hskip.03cm $\Omega(C_1 \oplus A_m,t+1)$ \hskip.03cm can have negative
coefficients for \hskip.03cm $m\ge 20$.
We refer to~\cite{LT} for more
on this example and to~\cite{Liu} for the background on non-negative
Ehrhart polynomials and further references.  We refer to
\cite{Cha} for $q$-Ehrhart polynomials, and to~\cite{KS} for further
results.


\smallskip

\subsection{Geometric form of the Kahn--Saks conjecture}\label{ss:finrem-KS}
One can ask if a version of the Kahn--Saks Conjecture~\ref{conj:KS-mon}
holds for general integral polytopes:
\begin{equation}\label{eq:KS-Ehr}
\text{Is} \quad \mathrm{Ehr}(Q,t-1)/t^d \quad \text{weakly decreasing for all} \ \ Q\in \mathbb R^d \ \ \text{and} \ \ t \in \mathbb N_{\ge 1} \. ?
\end{equation}
First, recall the example of
\defng{Reeve's tetrahedron} with vertices
at
$$
(0,0,0) \,, \quad (1,0,0) \,, \quad (0,1,0) \quad \text{and} \quad (1,1,h),
$$
see e.g.\ \cite[Ex.~3.23]{BR} and \cite[$\S$4.1]{GW}.  In this case,
the Ehrhart polynomial has negative signs, and the scaled Ehrhart polynomial
is non-monotone for large values of~$h$.  This shows that the
\defng{geometric Kahn--Saks conjecture}~\eqref{eq:KS-Ehr} does not hold for general lattice polytopes.

On the other hand, it is rather plausible that~\eqref{eq:KS-Ehr} holds for
\defng{antiblocking} (\defng{corner}) \defng{polytopes} \hskip.03cm
(see e.g.~\cite[$\S$5.9]{Sch}) with integer vertices.
If true, this would imply the Kahn--Saks Conjecture~\ref{conj:KS-mon}.  Indeed,
although the order polytope $\hskip.03cm \mathcal{O}_P$ \hskip.03cm is not antiblocking, the
\defng{stable set} (\defng{chain}) \defng{polytope} \hskip.03cm $\mathcal{C}_P$ \hskip.03cm is both
altiblocking and has the same Ehrhart polynomial by Stanley's theorem:  \hskip.03cm
$\mathrm{Ehr}(\mathcal{C}_P,t) = \mathrm{Ehr}(\mathcal{O}_P,t)$, see~\cite{Sta-two}.

Finally, let us
mention that the proof of Proposition~\ref{prop:scaled} can be modified to show that
$$\frac{1}{t^d} \. \mathrm{Ehr}(Q,t-1) \, \ge \, \frac{1}{(k \hskip.03cm t)^d} \.\mathrm{Ehr}(Q,kt-1)\hskip.03cm,
$$
for all antiblocking polytopes \hskip.03cm $Q\in \mathbb R^d$ \hskip.03cm with integer vertices.
This gives some credence to our speculation~\eqref{eq:KS-Ehr} in this case.

\smallskip

\subsection{Log-concavity and $q$-log-concavity}\label{ss:finrem-log}
The log-concavity for order polynomials proved in Theorem~\ref{thm:log-concave}
is somewhat different from other log-concave inequalities, see e.g.\ \cite{Bra,Huh,CP,Sta2}.
The $q$-log-concavity in Corollary~\ref{c:q-log-concavity} is also classical albeit
less studied, see e.g.\ \cite{Kra,Ler,Sag}.

\smallskip

\subsection{Sidorenko inequality}\label{ss:finrem-sid}
Note that another combinatorial proof of Sidorenko's inequality (Theorem~\ref{t:sid}) 
was independently found in \cite[$\S$4.1]{GG}, where the authors 
gave an elegant explicit construction of a surjection proving~\eqref{eq:sid}.  Unfortunately, 
the proof of correctness of that surjection is technical and cannot be easily inverted 
to obtain the desired injection.
More precisely, the authors give a explicit surjection \.
$\alpha: \mathcal E(P_\sigma)\times \mathcal E\bigl(P_{\overline{\sigma}}\bigr) \to S_n$\hskip.03cm.  
Unfortunately, the proof in~\cite{GG} is technical and indirect, 
so an explicit injection requires further effort.  

As we mentioned in the introduction, our injection~$\beta$ defined implicitly 
in the proof of Theorem~\ref{t:sid} likely coincides with an explicit injection
in~\cite{GG1}, since both essentially reverse engineer and make effective 
the original proof by Sidorenko~\cite{Sid}.  The connection with the argument 
in~\cite{StR} and the surjection in~\cite{MPP} in the case of \emph{Fibonacci posets} 
remains unclear.  

We also conjecture that the function \. $u: S_n \to \mathbb N$ \.
defined by~\eqref{eq:Sid-function} \hskip.03cm is \. ${\textsc{\#P}}$-complete.
The conjecture would follow if ${\textsc{\#P}}$-completeness was proved for self-dual
$2$-dimensional posets $P\simeq \overline{P}$. Unfortunately, the construction
in~\cite{DP} is too specialized and technical to obtain this result.

Finally, there a $q$-analogue of Sidorenko's inequality in~\cite[Cor.~3]{GG} 
generalizing $q$-equality for the series-parallel posets given 
in~\cite{Wei}.  See also~\cite{KS} for the definition of $e_q(P)$ for 
general~$P$ based on the $P$-partition theory, and~\cite{BW} for many 
other results on~$e_q(P)$.  


\smallskip

\subsection{Mixed Sidorenko inequality}\label{ss:finrem-mixed-sid}
In~\cite{BBS}, Bollob\'as, Brightwell and Sidorenko showed how to obtain Sidorenko's
Theorem~\ref{t:sid} via a known special case of \defng{Mahler's Conjecture}.
Most recently, Artstein-Avidan, Sadovsky and Sanyal extended this approach
in~\cite{AASS} to obtain the following remarkable generalization of the
Sidorenko inequality.

For two posets \. $P=(X,\prec)$ \. and \. $Q=(X,\prec')$ \. on the same set,
\defn{mixed linear extensions} are triples \hskip.03cm $(f,g,J)$, where \.
$J\subset [n]$, \. $f\in \mathcal E(P|_J)$, and \. $g\in \mathcal E\bigl(Q|_{\overline{J}}\bigr)$. Denote
by \hskip.03cm $e_k(P,Q)$ \hskip.03cm the number of such triples with $|J|=k$, i.e.\
$$
e_k(P,Q) \ := \ \sum_{J\in \binom{[n]}{k}} \. e(P|_J) \. e\bigl(Q|_{\overline{J}}\bigr).
$$

\begin{thm}[{\rm \cite[Thm~6.2]{AASS}}{}] \label{t:sid-mxed}
Let \. $P, Q, S, T$ \. be four posets on the same ground set, such that \. $|C\cap C'|\le 1$ \. and \. $|D\cap D'|\le 1$,
for all \. $C\in \mathcal C(P)$, \. $C'\in \mathcal C(Q)$,  \. $D\in \mathcal C(S)$ \. and \. $D'\in \mathcal C(T)$.
Then we have:
\begin{equation}\label{eq:sid-mixed}
e_k(P,Q) \, e_k(S,T) \ \ge \ n!\.\hskip.03cm \binom{n}{k}\hskip.03cm.
\end{equation}
\end{thm}

It would be interesting to find a combinatorial proof of this result.
It would be even more interesting to find a direct injective proof, and
conclude that the function giving the difference of the two sides of~\eqref{eq:sid-mixed}
is in~$\hskip.03cm {\textsc{\#P}}$.  The results in~\cite{IP} suggest that this might not be possible.
Finally, does the \defn{mixed Sidorenko inequality}~\eqref{eq:sid-mixed} have an upper bound
similar to that in~\cite{BBS}?

\smallskip

\subsection{Complexity of correlation inequalities}\label{ss:finrem-more}
By taking the limit \. $t\to \infty$ \. in Lemma~\ref{l:main order polynomial}, we obtain:
\begin{equation}\label{eq:min-min} \tag{$\ast$}
(n-1) \. \cdot \. e(P) \. \cdot \. e\bigl(P \smallsetminus \{x,y\}\bigr)  \ \geq \ n \. \cdot \. e\big(P \smallsetminus x\big)  \. \cdot \.  e\big(P\smallsetminus y\big).
\end{equation}
It would be interesting to see if this inequality can be proved injectively.
Is the function giving the difference of the two sides of this inequality in~$\hskip.03cm {\textsc{\#P}}$?

Note that, by applying the negative-correlation version of the
FKG inequality to the proof of Lemma~\ref{l:main order polynomial},
we obtain the following result:

\begin{lemma}\label{l:OP min-max}
	Let \. $P=(X,\prec)$ \. be a poset, let \. $x\in X$ \. be a minimal element, and let \. $y \in X$ \. be a maximal element such that $y$ does not cover~$x$.
	Then, for every integer $t>0$, we have:
	\[ {\Omega\big(P,\hskip.03cm t\big)} \. \cdot \. {\Omega\big(P \smallsetminus \{x,y\},\hskip.03cm t\big)}  \ \leq \  {\Omega\big(P \smallsetminus x, \hskip.03cm t\big)}  \. \cdot \.  {\Omega\big(P\smallsetminus y,\hskip.03cm t\big)}.
	\]
\end{lemma}

By taking the limit \. $t\to \infty$ \. in the lemma, we get the inequality opposite to~\eqref{eq:min-min}:
\begin{equation}\label{eq:min-max} \tag{$\ast\ast$}
(n-1) \. \cdot \. e(P) \. \cdot \. e\bigl(P \smallsetminus \{x,y\}\bigr)  \ \leq \ n \. \cdot \. e\big(P \smallsetminus x\big)  \. \cdot \.  e\big(P\smallsetminus y\big).
\end{equation}
Of course, the element $y$ was minimal in~\eqref{eq:min-min} and is maximal in~\eqref{eq:min-max},
but these inequalities are striking in appearance.  Again, it would be interesting to see if this
inequality can be proved injectively.

\smallskip

\subsection{Vanishing and uniqueness conditions}\label{ss:finrem-vanishing}
Note that the vanishing conditions for the Stanley inequality are a
special case of the \defna{equality conditions}, which are fully described
in~\cite{SvH} and reproved in~\cite{CP}.  For example, Corollary~\ref{cor:antichain}
and Corollary~\ref{c:sid-equality} give further examples of equality conditions,
with a simple proof in both cases via direct injection.  When there is no injective
proof, the equality condition can become a major challenge.

For example, for the \defng{Kahn--Saks inequality} generalizing Stanley's inequality, the
equality conditions remain open in full generality.  See, however, \cite[$\S$8]{CPP2}
for the vanishing conditions of the Kahn--Saks inequality, proved also via the promotion
technology.  See also \cite{CPP1,CPP2},
for the equality conditions of the Kahn--Saks and cross-product inequalities
for posets of width two.  Finally, let us mention Lemma~14.6 in~\cite{CP}, which is
yet another variation on Theorem~\ref{t:LE-gen-transitive} and proved by a direct
combinatorial argument using promotions.

In a different direction, sometimes the equality conditions are trivial as the
natural inequalities are always strict except for some degenerate cases.
This is the case with the \defng{XYZ inequality}~\cite{Fish}, and the
\defng{log-concavity} (Theorem~\ref{thm:log-concave-strict}) discussed above.


The uniqueness conditions are studied less frequently than vanishing and equality
conditions, since they tend to be harder.  For example, there is no description of
the uniquely colorable graphs, and this remains a major open problem~\cite{CZ}.
Notable positive results include uniqueness conditions for the \defng{Kostka
numbers}~\cite{BZ} and for the \defng{Littlewood--Richardson coefficients}
\cite[Prop.~3.13]{BI}.

\smallskip


\subsection{Poset dynamics}\label{ss:finrem-algebraic}
Promotions, demotions and evacuations were defined by Sch\"utzenberger in~\cite{Sch},
and this approach has been immensely influential leading to the \defng{RSK Algorithm} \hskip.03cm
and the \defng{Edelman--Greene bijection}, among other things.
Group theoretic approach in the context of combinatorics of words were
developed by Lascoux and Sch\"utzenberger, and specifically in the generality
of posets were introduced by Haiman~\cite{Hai} and Malvenuto--Reutenauer~\cite{MR}.
See also~\cite{KB} for a related approach in the context of semistandard Young
tableaux, and~\cite{Sta-promo} for an extensive survey.

It would be interesting to find a generalization of the evacuation~$\varepsilon$ which would
preserve its involution property.  Such
``restricted evacuation'' might give rise to ``restricted domino linear
extensions'' which would be of independent interest,
see e.g.~\cite[$\S$3]{Sta-promo}.

The extension of promotion to general bijections \. $X\to [n]$ \. was obtained
in~\cite{DK}.  Can our group action on restricted linear extensions be
generalized in this direction?  Note that we have only limited
understanding if the group action can be applied to study the
order polynomial.  See however~\cite{Hop} for some elegant
product formulas in some special cases.

The promotion operators were used in~\cite{AKS} to define a Markov chain on
the set \hskip.03cm $\Ec(P)$ \hskip.03cm of linear extensions of a given poset~$P$.
See also~\cite{RS} where a related Markov chain was shown to be
mixing in time \hskip.03cm $O(n \log n)$.  It would be interesting to see if these
results can be generalized to show that the restricted linear extensions in
\. $\Ec(P,\textbf{\textit{x}}, \textbf{{\textit{a}}})$ \. can be sampled in polynomial time.

Finally, let us mention a curious loop-free listing algorithm in~\cite{CW}.
Is there a similar algorithm for the restricted linear extensions?

\smallskip

\subsection{Injections and matchings for the Stanley inequality}\label{ss:finrem-GP-injection}
As we mentioned in the introduction, it remains a major open problem whether
Stanley's inequality~\eqref{eq:Sta} can be proved by a direct injection,
see e.g.~\cite[$\S$17.17]{CP}.  Formally, in the notation of Theorem~\ref{t:Sta},
let
$$
\rho(P,x,a) \ := \ \textrm{N}(P, x,a)^2 \, - \, \textrm{N}(P, x,a+1) \.\cdot \.  \textrm{N}(P, x,a-1)\hskip.03cm.
$$

\begin{op} \label{op:Sta-SP}
Is \. $\rho \hskip.03cm \in \. {\textsc{\#P}}$?
\end{op}

At this point, it is even hard to guess which way
the answer would go.  While some of us believe the answer should be negative,
others disagree.  The only thing certain is that none of the positive proofs
in~\cite{CP,Sta-AF} imply a positive answer, while the negative results in~\cite{IP}
are not even close to resolving the problem.  Since part of the motivation behind
our algebraic approach aimed at resolving this problem, let us propose the following
approach.

\smallskip

We would like to give an injection proving Stanley's inequality~\eqref{eq:Sta}.
Consider the following family of elements of the group $G$ from Section~\ref{s:restricted} whose actions would be good
candidates for such an injection.
Let\. $\mathcal{G}=(V\sqcup W,E)$ \. be a bipartite graph, where \.
$V=\Ec(P,x,a) \times \Ec(P,x,a)$ \. and \. $W= \Ec(P,x,a-1) \times \Ec(P,x, a+1)$.
We define the set~$E$ of edges as follows.

Let \. $\pi \in \Ec(P,x,a-1)$ \. and \. $\sigma \in \Ec(P,x,a+1)$, so that \. $(\pi,\sigma) \in W$.
For every element \hskip.03cm $y$ \hskip.03cm which appears after \hskip.03cm $x$ \hskip.03cm in \hskip.03cm $\pi$ and before \hskip.03cm $x$ \hskip.03cm in \hskip.03cm $\sigma$,
that is \. $i:=\pi^{-1}(y) > a-1$ \. and \. $j:=\sigma^{-1}(y) <a+1$, we apply the
promotion/demotion operators on the chain starting/ending at~$y$ in $\sigma$ and $\pi$, respectively.
Let \. $\bar{\delta}_j := \tau_{n-1}\cdots \tau_j$.  Then in the word \hskip.03cm $\delta_i \pi$,
the chain starting at~$y$ is pushed up, so that~$x$ is moved to position~$a$. Similarly,
in the word \. $\bar{\delta}_j \sigma$, the chain ending at~$y$ is pushed down,
so that~$x$ is moved to position $a$. Thus \. $(\delta_i \pi, \bar{\delta}_j\sigma) \in \Ec(P;a;x) \times \Ec(P;a;x) = V$,
and we connect it to \hskip.03cm $(\pi,\sigma)$ \hskip.03cm by an edge. Note that by the pigeonhole principle,
there are at least two possibilities for elements~$y$, and thus there will be at least one edge,
however it is not necessarily true that the degree of every \hskip.03cm $(\pi,\sigma)$ \hskip.03cm is at least~$2$.

\begin{conj}
Let \. $\mathcal{G}=(V\sqcup W, E)$ \. be the graph defined above.
Then there exists a maximal matching which covers all vertices in~$W$.
\end{conj}

This matching will be the desired injection and imply the Stanley inequality.
By itself, the conjecture would not imply that \. $\rho\hskip.03cm \in\. {\textsc{\#P}}$\hskip.03cm.
For that, the injection would need to be computable in polynomial time.

\vskip.5cm


\subsection*{Acknowledgements}
We are grateful to Nikita Gladkov, F\"edor Petrov, Yair Shenfeld and Ramon van Handel
for helpful discussions and remarks on the subject.  Matt Beck, Fu Liu and Sinai Robins
kindly helped us with the Ehrhart polynomial questions.  We thank Christian Gaetz and 
Yibo Gao for help with the references.  Over the years,  
we held numerous conversations with Christian Ikenmeyer on complexity,
and the knowledge we acquired has been indispensable.

We thank Vic Reiner for sharing his proof of Theorem~\ref{t:HP-q}
with us and generously allowing us to publish it.  We also thank
Sam Hopkins for telling us about Exc.~3.143 in \cite{Sta-EC} (see
Remark~\ref{r:comp}).  Special thanks to
Richard Stanley for resolving the mystery where Exc.~3.57 comes from,
and telling us about Exc.~3.163 in \cite{Sta-EC}.  We continuously
regret not memorizing all the exercises in~\cite{Sta-EC}.

Finally, we owe a dept of gratitude
to Yufei Zhao who convinced us not to initialize first names
in the references, a practice we followed for years.  It is the right
thing to do and we urge others to follow the suit.\footnote{For more on this, see
Yufei~Zhao,
How I manage my {\tt BibTeX} references, and why I prefer not initializing first names,
\hskip.03cm \href{https://yufeizhao.com/blog/2021/07/04/bibtex/}{personal blog post} \hskip.03cm (July 4, 2021).}
This research was partially done while the third author was enjoying MSRI's hospitality in Fall of~2021.
The first author was partially supported by the Simons Foundation.
The second and third authors were partially supported by the~NSF.
\newpage





	

2022-05-25T02:07:33.000
2205
2205.02798
en
https://arxiv.org/abs/2205.02798
We explore inequalities on linear extensions of posets and make them effective in different ways. First, we study the Björner--Wachs inequality and generalize it to inequalities on order polynomials and their $q$-analogues via direct injections and FKG inequalities. Second, we give an injective proof of the Sidorenko inequality with computational complexity significance, namely that the difference is in $\#P$. Third, we generalize the Sidorenko inequality to posets with small chain intersections and give complexity theoretic applications.
Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)
Effective poset inequalities
Qwen/Qwen-72B
1. YES
2. YES