\documentclass[finalversion]{FPSAC2020}
\articlenumber{54}
\addbibresource{fpsac.bib}


\usepackage{tikz}
\usepackage{euscript, mathrsfs,amscd} 
\usepackage{epsfig}
\usepackage{blkarray}
\usepackage{multirow}
\usepackage{mathtools}
\usepackage{bm}
\usepackage{ytableau}
\usepackage{caption}
\usepackage{hyperref}
\usepackage{cases}
\usepackage{enumitem}

\usepackage{subfigure}
\usepackage{graphicx} %ifpdf

\usetikzlibrary{decorations.markings}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rem}[thm]{Remark}

%-------- Meta Data ------------------------------------------

\title{Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions}

\author[H.-H.~Hwang, W.-S.~Jung, K.-J.~Lee, J.~Oh, and S.-H.~Yu]{Byung-Hak Hwang\thanks{\href{mailto:xoda@snu.ac.kr}{xoda@snu.ac.kr}.}\addressmark{1}, Woo-Seok Jung\thanks{\href{mailto:jungws@sogang.ac.kr}{jungws@sogang.ac.kr}.}\addressmark{2}, Kang-Ju Lee\thanks{\href{mailto:leekj0706@snu.ac.kr}{leekj0706@snu.ac.kr}.}\addressmark{3},\\ Jaeseong Oh\thanks{\href{mailto:jaeseong_oh@snu.ac.kr}{jaeseong\_oh@snu.ac.kr}.}\addressmark{1}, \and Sang-Hoon Yu\thanks{\href{mailto:ysh4017@snu.ac.kr}{ysh4017@snu.ac.kr}.}\addressmark{1}}

\address{\addressmark{1}Department of Mathematical Sciences, Seoul National University, Seoul,
South Korea \\ \addressmark{2}Department of Mathematics, Sogang University, Seoul,
South Korea \\ \addressmark{3}Department of Mathematical Sciences and Research Institute of Mathematics, Seoul
National University, Seoul, South Korea}


%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

\abstract{We define the acyclic orientation polynomial of a graph to be the generating function for the sinks of its acyclic orientations. Stanley proved that the number of acyclic orientations is equal to the chromatic polynomial evaluated at $-1$ up to sign. Motivated by this result, we develop ``acyclic orientation'' analogues for theorems concerning the chromatic polynomial by Birkhoff, Whitney, and Greene--Zaslavsky. As the main application, we provide a new proof for Stanley's sink theorem for chromatic symmetric functions $X_G$, which gives a relation between the number of acyclic orientations with a fixed number of sinks and the coefficients in the expansion of $X_G$ with respect to elementary symmetric functions.}

\keywords{acyclic orientations, the generating function for sinks, deletion-contraction recursion, the sink theorem, chromatic symmetric functions}


\begin{document}

\maketitle

\section{Introduction}
The purpose of this paper is to introduce acyclic orientation polynomials, present their several expressions, and give a new proof for Stanley's sink theorem from these expressions. Throughout this paper, let $G=(V,E)$ be a simple graph with $|V|=d$ vertices. The variable associated to a vertex $v \in V$ will be denoted by the same notation $v$. 

Our object of study is an \emph{acyclic orientation} of the graph $G$, an assignment of a direction to each edge so that the orientation induces no directed cycles. Denote by $\mathcal{A}(G)$ the collection of acyclic orientations of $G$. The number of acyclic orientations of $G$ is a Tutte-Grothendieck invariant, i.e., this number obeys a \emph{deletion-contraction} recursion. As a refinement of the quantity, we introduce the \emph{acyclic orientation polynomial} (\cref{def:AOP}). For $\mathfrak{o} \in \mathcal{A}(G)$, let $\operatorname{Sink}(G,\mathfrak{o})$ be the set of sinks of $\mathfrak{o}$, and define the acyclic orientation polynomial $A_G(V)$ to be
\[
A_G(V)=\sum_{\mathfrak{o}\in \mathcal{A}(G)}\prod_{v \in \operatorname{Sink}(G,\mathfrak{o})}{v}.
\]
Specializing $v=t$ for all $v \in V$ in our polynomial $A_G(V)$, one obtains   the polynomial $a_G(t)$ whose coefficient of $t^j$ counts the number of acyclic orientations with $j$ sinks \cite{Stanley95, Lass01}. We prove that $A_G(V)$ satisfies the deletion-contraction recurrence (\cref{thm:DC}) with a change of variables:
\begin{equation}\label{eq:intro_v_e}
v_e=u_1+u_2-u_1u_2, \mbox{ or equivalently } 1-v_e=(1-u_1)(1-u_2), 
\end{equation}
where $v_e$ is the vertex of the graph $G/e$ obtained from $G$ by contracting an edge $e=u_1u_2 \in E$.

Using this deletion-contraction recurrence, we shall give several expressions for $A_G(V)$. Stanley  \cite{Stanley73} showed that the number of acyclic orientations of $G$ is equal to $(-1)^d{\chi_G(-1)}$, where $\chi_G(n)$ is the chromatic polynomial of $G$ and $d$ is the number of vertices. This result motivates us to develop ``acyclic orientation'' analogues for theorems concerning $\chi_G(n)$. Let us recall four famous expressions for the chromatic polynomial $\chi_G(n)$:
\begin{align}
\chi_G(n)
&= \sum_{S \subseteq E}(-1)^{|S|} n^{c(S)} && \mbox{[The subgraph expansion]} \\ 
&= \sum_{S \in B_G}(-1)^{|S|} n^{c(S)} && \mbox{{\cite[Whitney's Theorem]{Whitney32}}} \\ 
&= \sum_{\pi \in L_G}\mu_G(\hat{0},\pi) n^{|\pi|} && \mbox{{\cite[Birkhoff's Theorem]{Birk12}}} \\ 
&= \sum_{\mathfrak{o} \in \mathcal{A}(G)}(-1)^{d-|\pi(\mathfrak{o})|} n^{|\pi(\mathfrak{o})|} && \mbox{{\cite[Corollary 7.4]{GZ83}}}, 
\end{align}
where $S\subseteq E$ is a spanning subgraph of $G$, $c(S)$ is the number of connected components of $S$, $B_G$ is the broken circuit complex, $L_G$ is the bond lattice and $\mu_G$ is the M\"{o}bius function of $L_G$, and $\pi:\mathcal{A}(G) \to L_G$ is the map defined in \cite[Section 4]{BN19}.

Similarly for the chromatic polynomial, we provide four expressions for $A_G(V)$:
\begin{align*}
A_G(V) &= \sum_{S \subseteq E}(-1)^{s(S)}\prod_{C \in \mathcal{C}(S)}v_C && \mbox{[\cref{thm:AC_Sub}]} \\ 
&= \sum_{S \in B_G}\prod_{C \in \mathcal{C}(S)}v_C && \mbox{[\cref{thm:AC_BC}]} \\
&= \sum_{\pi \in L_G}(-1)^{d-|\pi|}\mu_G{(\hat{0},\pi)}\prod_{B \in \pi}{v_B} && \mbox{[\cref{thm:AC_LG}]}\\ 
&= \sum_{\mathfrak{o} \in \mathcal{A}(G)}\prod_{ B \in \pi(\mathfrak{o})}v_{B} && \mbox{[\cref{thm:AC_SD}]},
\end{align*}
where $\mathcal{C}(S)$ is the set of connected components of a subgraph $S$ and $s(S)=|S|-d+c(S)$ is the corank of $S$. To a connected component $C$ and a vertex subset $B$, we associate variables 
\[
v_C=1-\prod_{v \in V(C)}(1-v) \quad\mbox{and}\quad v_B=1-\prod_{v \in B}(1-v),
\]
which are generalizations of \eqref{eq:intro_v_e}. Comparing above expressions for $\chi_G(n)$ and $A_G(V)$, we can see that replacing $n$ by $-v_C$ or $-v_B$ in expressions for the chromatic polynomial gives the acyclic orientation polynomial (up to sign).

Various known results for acyclic orientations are represented as coefficients in our expressions for $A_G(V)$. The linear terms (\cref{cor:unique,cor:unique2}) give \cite[Theorem 7.3]{GZ83}, which says that the number of acyclic orientations with the unique sink at a fixed $v \in V$ equals the M\"obius invariant. Using \cite[Theorem 7.3]{GZ83} and Weisner's theorem, we present an alternative proof for \cref{thm:AC_LG}. Comparing \cref{thm:AC_LG,thm:AC_SD} yields \cite[Theorem 7.4]{GZ83} representing the cardinalities of images under the map $\pi$ in terms of M\"obius functions. Note that this theorem gives an expression for the number of acyclic orientations whose sinks are in $U \subseteq V$, which is directly derived from our expression for $A_G(V)$.

The main application of our expressions for $A_G(V)$ is to give a \emph{new} proof of the sink theorem \cite[Theorem 3.3]{Stanley95} for the chromatic symmetric function $X_G$. The theorem asserts 
\begin{equation*}
\operatorname{sink}(G,j)=\sum_{\substack{\lambda  \, \vdash \,  d \\ l(\lambda)=j}}c_\lambda,
\end{equation*}
where $\operatorname{sink}(G,j)$ is the number of acyclic orientations of $G$ with $j$
sinks, the numbers $c_{\lambda}$ are defined by the expansion $X_G=\sum_{\lambda  \,  \vdash  \,  d}c_{\lambda}e_{\lambda}$ in terms of elementary symmetric functions $e_{\lambda}$, and $l(\lambda)$ is the length of a partition $\lambda$. The original proof relies on the theory of quasi-symmetric functions and $P$-partitions, which inspired Stanley \cite{Stanley99, Stanley12} to ask for a simple and conceptual proof for the theorem. Also we analyze how $A_G(V)$ and $a_G(t)$ distinguish graphs.

\section{Acyclic orientation polynomials and their recurrence}\label{sec:AC_DC} 
Let $G$ be a graph with the vertex set $V=V(G)$ and the edge set $E=E(G)$. In this paper, let $|V|=d$ and assume that $G$ is simple, i.e., $G$ has no loops or multiple edges. For an edge $u_1u_2 \in E$, a direction $\overrightarrow{u_1u_2}$ (resp. $\overrightarrow{u_2u_1}$) means that the oriented edge is toward $u_2$ (resp. $u_1$). An orientation $\mathfrak{o}$ is an assignment of a direction $\overrightarrow{u_1u_2}$ or $\overrightarrow{u_2u_1}$ to each edge $u_1u_2 \in E$. An orientation $\mathfrak{o}$ is said to be \emph{acyclic} if $\mathfrak{o}$ has no directed cycles. Let $\mathcal{A}(G)$ be the set of acyclic orientations of $G$. For $\mathfrak{o} \in \mathcal{A}(G)$, a \emph{sink} of $\mathfrak{o}$ is a vertex $v$ such that the direction of each edge incident to $v$ is toward to $v$. Let $\operatorname{Sink}(G,\mathfrak{o})$ be the set of sinks of an orientation $\mathfrak{o}$ and $\operatorname{sink}(G,\mathfrak{o})=|\operatorname{Sink}(G,\mathfrak{o})|$. 

We associate a variable to each vertex $v \in V$, and use the same notation $v$ for this variable. Then $V$ also denotes the set of the variables corresponding to vertices. Assume that all the variables commute with each other.

We now introduce the definition of the main object in this paper.
\begin{defn}\label{def:AOP}
 For a graph $G=(V,E)$, define the \emph{acyclic orientation polynomial} $A_G(V)$ of $G$ to be the generating function for sinks of acyclic orientations of $G$, i.e.,
\[
A_G(V)=\sum_{\mathfrak{o}\in \mathcal{A}(G)}\prod_{v \in \operatorname{Sink}(G,\mathfrak{o})}{v}.
\]
Let $a_G(t)$ be the polynomial obtained from $A_G(V)$ by setting $v=t$ for each $v \in V$, i.e.,
\[
a_G(t)=\sum_{\mathfrak{o}\in \mathcal{A}(G)}t^{\operatorname{sink}(G,\mathfrak{o})}.
\]
\end{defn}

Take a non-empty subset $U$ of $V$. Let $\mathcal{A}(G,U)$ be the set of acyclic orientations $\mathfrak{o}$ of $G$ with $\operatorname{Sink}(G,\mathfrak{o})=U$. Then the coefficient of $\prod_{v \in U}v$ is equal to $|\mathcal{A}(G,U)|$, which will be denoted by $a(G,U)$. When $U$ consists of a single vertex $u$, we write $a(G,u)$ instead of $a(G,\{u\})$.

\begin{ex}\label{ex:two} Let us consider two graphs $G_1=(\{v_1,v_2,v_3\},\{v_1v_2,v_2v_3,v_3v_1\})$ and $G_2=(\{v_1,v_2,v_3,v_4\},\{v_1v_2,v_2v_3,v_3v_1,v_1v_4\})$. Their acyclic orientation polynomials are
\begin{eqnarray*}
A_{G_1}(\{v_1,v_2,v_3\})
&=&
2(v_1+v_2+v_3), \mbox{ and} \\
A_{G_2}(\{v_1,v_2,v_3,v_4\})
&=&
2(v_1+v_2+v_3+v_4+v_2v_4+v_3v_4).
\end{eqnarray*}
In \cref{fig:AO_G_2}, we list all the acyclic orientations of $G_2$ with corresponding monomials.
\end{ex}


\begin{figure}[h]
\centering
\resizebox{.9\linewidth}{!}{
\begin{tabular}{cccccc}
%-------01_____v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.355,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.35},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_1$}};
\end{tikzpicture}&
%-------02_____v3-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_1$}};
\end{tikzpicture}&
%-------03_____v2v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_2$}};
\end{tikzpicture}&
%-------04_____v2-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_2$}};
\end{tikzpicture}&
%-------05_____v2v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_3$}};
\end{tikzpicture}&
%-------06_____v2-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] ({sqrt(3)},0) -- (0,1);
\end{scope}

\node at (0,-2) {\Huge{$v_3$}};
\end{tikzpicture}\\
%-------07_____v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_4$}};
\end{tikzpicture}&
%-------08_____v3-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_4$}};
\end{tikzpicture}&
%-------09_____v1v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_2v_4$}};
\end{tikzpicture}&
%-------10_____v1-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (0,-1) -- (0,1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_3v_4$}};
\end{tikzpicture}&
%-------11_____v1v4-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (0,1) -- (-{sqrt(3)},0);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_3v_4$}};

\end{tikzpicture}&
%-------12_____v1-----------------
\begin{tikzpicture}[scale=0.50,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill (0,-1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\LARGE{$v_1$}};
\node at (-{sqrt(3)}-0.35,0) {\LARGE{$v_2$}};
\node at (0,-1.3) {\LARGE{$v_3$}};
\node at ({sqrt(3)+0.3},0) {\LARGE{$v_4$}};
%------------------------------
\begin{scope}[decoration={
    markings,
    mark=at position 0.50 with {\arrow{latex}}}
    ] 
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,1);
\draw[postaction={decorate}] (-{sqrt(3)},0) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- (0,-1);
\draw[postaction={decorate}] (0,1) -- ({sqrt(3)},0);
\end{scope}

\node at (0,-2) {\Huge{$v_3v_4$}};

\end{tikzpicture}
\end{tabular}
}
    \caption{Acyclic orientations of $G_2$ with corresponding monomials below.} \label{fig:AO_G_2}
\end{figure}

We show that the acyclic orientation polynomial $A_G(V)$ satisfies the deletion-contrac\-tion recurrence with \emph{a change of variables}. Our theorem generalizes the fact that the number of acyclic orientations satisfies the deletion-contraction recurrence. Take an edge $e=u_1u_2 \in E(G)$. The deletion $G \setminus e$ is the graph obtained from $G$ by deleting $e$. The contraction $G/e$ is the graph obtained from $G$ by contracting $e$ and replacing all resulting multiple edges by a single edge so that $G/e$ is simple. Let $v_e$ be the vertex created by contracting $e$ and let the variable $v_e$ satisfy the following relation: 
\begin{equation*}
v_e=1-(1-u_1)(1-u_2)=u_1+u_2-u_1u_2.
\end{equation*}
For simplicity, denote $V(G/e)$ by $V/e$.
\begin{thm}\label{thm:DC}
The acyclic orientation polynomial $A_G(V)$ satisfies the deletion-contraction recurrence: for every $e\in E(G)$,
\begin{equation*}
A_{G}(V)=A_{G\setminus e}(V)+A_{G/e}(V/e).
\end{equation*}
\end{thm}

\begin{ex}\label{ex:SGF} Let $H$ be the graph whose vertex set is $V(H)=\{v_1,v_2,v_3,v_4\}$ and edge set is $E(H)=\{v_1v_2,v_2v_3,v_3v_1,v_1v_4,v_3v_4\}$. The graphs $H,H\setminus v_3{v_4}$, and $H/v_3{v_4}$ are shown in \cref{fig:G1G2H}. Using the deletion-contraction recurrence together with the computations in \cref{ex:two}, we obtain
\begin{eqnarray*}
A_H(V)&=&A_{H\setminus v_3{v_4}}(V)+A_{H/v_3{v_4}}(\{v_1,v_2,v_{34}=v_3+v_4-v_3v_4\}) \\
&=&
 2(v_1+v_2+v_3+v_4+v_2v_4+v_3v_4)+2(v_1+v_2+v_3+v_4-v_3v_4)
\\
&=&
4(v_1+v_2+v_3+v_4)+2v_2v_4, 
\end{eqnarray*}
and hence we have $a_H(t)=16t+2t^2$.
\end{ex}

\begin{figure}[h]
\centering
\resizebox{.9\linewidth}{!}{
\setlength{\tabcolsep}{25pt}
    \begin{tabular}{ccc}

\begin{tikzpicture}[scale=0.8,every node/.style={transform shape}] \fill (0,1) circle (2pt); \fill (0,-1) circle (2pt); \fill ({sqrt(3)},0) circle (2pt); \fill (-{sqrt(3)},0) circle (2pt); \node at (0,1.3) {\Large{$v_1$}}; \node at (-{sqrt(3)}-0.35,0) {\Large{$v_2$}}; \node at (0,-1.3) {\Large{$v_3$}}; \node at ({sqrt(3)+0.3},0) {\Large{$v_4$}}; 
%------------------------------ 
\draw (0,1) -- (-{sqrt(3)},0); \draw (-{sqrt(3)},0) -- (0,-1); \draw (0,1) -- (0,-1); \draw ({sqrt(3)},0) --(0,1); \draw ({sqrt(3)},0) --(0,-1); 
\node at (0,-2) {\large $H$};
\end{tikzpicture} 
&
\begin{tikzpicture}[scale=0.8,every node/.style={transform shape}]
 \fill (0,1) circle (2pt); \fill (0,-1) circle (2pt); \fill ({sqrt(3)},0) circle (2pt); \fill (-{sqrt(3)},0) circle (2pt); \node at (0,1.3) {\Large{$v_1$}}; \node at (-{sqrt(3)}-0.35,0) {\Large{$v_2$}}; \node at (0,-1.3) {\Large{$v_3$}}; \node at ({sqrt(3)+0.3},0) {\Large{$v_4$}}; %------------------------------
 
\draw (0,1) -- (-{sqrt(3)},0); \draw (-{sqrt(3)},0) -- (0,-1); \draw (0,1) -- (0,-1); \draw ({sqrt(3)},0) --(0,1); 
\node at (0,-2) {\large $H\setminus v_3v_4$};
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.8,every node/.style={transform shape}] \fill (0,1) circle (2pt); \fill (0,-1) circle (2pt); \fill (-{sqrt(3)},0) circle (2pt); \node at (0,1.3) {\Large{$v_1$}}; \node at (-{sqrt(3)}-0.355,0) {\Large{$v_2$}}; \node at (0,-1.3) {\Large{$v_{34}$}}; \node at ({sqrt(3)+0.3},0) {\quad\quad}; 
%------------------------------ 
\draw (0,1) -- (-{sqrt(3)},0); \draw (-{sqrt(3)},0) -- (0,-1); \draw (0,1) -- (0,-1); 
\node at (0,-2) {\large $H/v_3v_4$};
\end{tikzpicture}
    \end{tabular}
}
    \caption{Graphs $H, H\setminus v_3v_4$, and $H/v_3v_4$.} \label{fig:G1G2H}
\end{figure} 

\section{Four expressions for acyclic orientation polynomials}\label{sec:Expression}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Subgraph expansions}\label{sec:Sub} We will expand our acyclic orientation polynomial $A_G(V)$ with respect to spanning subgraphs of $G$. Let $S$ be a subset of the edge set $E(G)$. The set $S$ will be identified with the spanning subgraph of $G$ whose edge set is $S$. Denote by $|S|$ the number of edges of $S$. Let $\mathcal{S}(G)$ be the collection of spanning subgraphs of $G$. For an edge $e=u_1u_2 \in E(G)$, define
\[
\mathcal{S}(G)^e=\{S \in \mathcal{S}(G)\, \mid\, e \notin E(S) \}, \mbox{ and } \mathcal{S}(G)_e=\mathcal{S}(G) \setminus \mathcal{S}(G)^e. 
\]

\begin{prop}\label{prop:AC_Sub} For an edge $e \in E(G)$, deleting $e$ yields $\mathcal{S}(G)^e=\mathcal{S}(G\setminus e)$ and contracting $e$ gives a bijection between $\mathcal{S}(G)_e$ and $\mathcal{S}(G/e)$. 
\end{prop}

Let $\mathcal{C}(S)$ be the set of connected components of a subgraph $S$. For each connected component $C \in \mathcal{C}(S)$, define the variable $v_C$ to be 
\[
v_C=1-\prod_{v \in V(C)}(1-v). 
\]
Note that $v_{C}={v_{e}}$, where $C$ is a graph with two vertices and one edge $e$. Let $s(S)$ be the \emph{corank} of $S$ defined as $s(S)=|S|-d+|\mathcal{C}(S)|$. 

\begin{thm}\label{thm:AC_Sub} For a graph $G=(V,E)$, its acyclic orientation polynomial $A_G(V)$ equals
\[
A_G(V)=\sum_{S \subseteq E}(-1)^{s(S)}\prod_{C \in \mathcal{C}(S)}v_C.
\]
Hence,
\begin{equation*}
a_G(t)=\sum_{S \subseteq E}(-1)^{s(S)}{\prod_{C \in \mathcal{C}(S)}{\big(1-(1-t)^{|V(C)|}\big)}}. 
\end{equation*}
\end{thm}

\begin{ex} Let $P$ be the path graph of length 2. See \cref{fig:path}. We can compute $\prod_{C \in \mathcal{C}(S)}v_C$ for each spanning subgraph $S$. For instance, let $S=\{v_1 v_2\}$ be the second subgraph in \cref{fig:path}. $S$ has the two connected components whose vertex sets are $\{v_1,v_2\}$ and $\{v_3\}$. Then the corresponding term is
\[
\prod_{C \in \mathcal{C}(S)}v_C = (1-(1-v_1)(1-v_2))v_3.
\]
Note that the corank of each subgraph of $P$ is equal to 0. Using the previous theorem, we have
\begin{align*}
A_P(V) &= (1-(1-v_1)(1-v_2)(1-v_3)) + (1-(1-v_1)(1-v_2))v_3 \\
&\quad + (1-(1-v_2)(1-v_3))v_1 + v_1 v_2 v_3 \\
 &= v_1 + v_2 + v_3 + v_1 v_3.
\end{align*}
\begin{figure}[h]
\centering
\resizebox{.9\linewidth}{!}{
\begin{tabular}{cccc}
%-------S={12,23}-----------------
\begin{tikzpicture}[scale=0.75,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\Large{$v_2$}};
\node at (-{sqrt(3)}-0.355,0) {\Large{$v_1$}};
\node at ({sqrt(3)+0.35},0) {\Large{$v_3$}};

\draw (-{sqrt(3)},0) -- (0,1);
\draw ({sqrt(3)},0) -- (0,1);

\node[scale=1.2] at (0,-1) {$1-(1-v_1)(1-v_2)(1-v_3)$};
\end{tikzpicture}&
%-------S={12}-----------------
\begin{tikzpicture}[scale=0.75,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\Large{$v_2$}};
\node at (-{sqrt(3)}-0.355,0) {\Large{$v_1$}};
\node at ({sqrt(3)+0.35},0) {\Large{$v_3$}};

\draw (-{sqrt(3)},0) -- (0,1);
% \draw ({sqrt(3)},0) -- (0,1);

\node[scale=1.2] at (0,-1) {$(1-(1-v_1)(1-v_2))v_3$};
\end{tikzpicture}&
%-------S={23}-----------------
\begin{tikzpicture}[scale=0.75,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\Large{$v_2$}};
\node at (-{sqrt(3)}-0.355,0) {\Large{$v_1$}};
\node at ({sqrt(3)+0.35},0) {\Large{$v_3$}};

% \draw (-{sqrt(3)},0) -- (0,1);
\draw ({sqrt(3)},0) -- (0,1);

\node[scale=1.2] at (0,-1) {$(1-(1-v_2)(1-v_3))v_1$};
\end{tikzpicture}&
%-------S={}-----------------
\begin{tikzpicture}[scale=0.75,every node/.style={transform shape}]
\fill (0,1) circle (1.5pt);
\fill ({sqrt(3)},0) circle (1.5pt);
\fill (-{sqrt(3)},0) circle (1.5pt);

\node at (0,1.3) {\Large{$v_2$}};
\node at (-{sqrt(3)}-0.355,0) {\Large{$v_1$}};
\node at ({sqrt(3)+0.35},0) {\Large{$v_3$}};

% \draw (-{sqrt(3)},0) -- (0,1);
% \draw ({sqrt(3)},0) -- (0,1);

\node[scale=1.2] at (0,-1) {$v_1 v_2 v_3$};
\end{tikzpicture}
\end{tabular}
}
    \caption{All spanning subgraphs of $P$ and their corresponding terms.} \label{fig:path}
\end{figure}
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Broken circuit complexes}\label{sec:AC_BC}
We will give an expression for $A_G(V)$ in terms of the broken circuit complex $B_G$ as an analogue of Whitney's theorem \cite{Whitney32}. Let the edge set $E(G)$ be linearly ordered. A broken circuit is a cycle with its smallest edge removed. The \emph{broken circuit complex} $B_G$ is the collection of all spanning subgraphs $S$ which do not contain a broken circuit. For an edge $e \in E(G)$, define
\[
(B_G)^e=\{S \in B_G\, \mid\, e \notin E(S) \}, \mbox{ and } (B_G)_e=B_G \setminus (B_G)^e. 
\]
\begin{prop}\label{prop:AC_BC} 
If $e\in E(G)$ is the largest edge in $E(G)$, then deleting $e$ yields $(B_G)^e=B_{G\setminus e}$ and contracting $e$ gives a bijection between $(B_G)_e$ and $B_{G / e}$. 
\end{prop}
\begin{thm}\label{thm:AC_BC} For a graph $G=(V,E)$, the acyclic orientation polynomial $A_G(V)$ equals
\begin{equation}\label{eq:AC_and_BC}
A_G(V)=\sum_{S \in B_G}\prod_{C \in \mathcal{C}(S)}v_C.
\end{equation}
\end{thm}

The linear terms of equation \eqref{eq:AC_and_BC} give the following corollary (\cite[Theorem 7.3]{GZ83}).
\begin{cor}[{\cite[Theorem 7.3]{GZ83}}]\label{cor:unique}
Let $G$ be a connected graph whose vertex set is $V$ with $|V|=d$. For any vertex $v \in V(G)$, the number of acyclic orientations of $G$ with the unique sink $v$ is equal to the number of no-broken-circuit sets with $d-1$ edges.
\end{cor}

\subsection{Bond lattices}\label{sec:AC_LG}
We express $A_G(V)$ in terms of the bond lattice $L_G$ as an analogue of Birkhoff's Theorem \cite{Birk12}. For a partition $\pi$ of a set, an element $B \in \pi$ is called a block. A \emph{bond} is a vertex partition each of whose blocks induces a connected graph. The set of bonds of $G$ forms the lattice $L_G$ partially ordered by refinement, called the \emph{bond lattice} of $G$. 

The least element $\hat{0}$ of $L_G$ is the bond each of whose blocks has only one vertex, and the greatest element $\hat{1}$ of $L_G$ is the bond each of whose blocks is the vertex set of a connected component of $G$. Let $\mu_G(\cdot,\cdot)$ be the M\"obius function of $L_G$. The \emph{M\"obius invariant} of $G$ is defined as $\mu(G)=|\mu_G(\hat{0},\hat{1})|$. Note that $|\mu_G(\hat{0},\pi)|=(-1)^{d-|\pi|}\mu_G(\hat{0},\pi)$ for $\pi \in L_G$.

\begin{prop}\label{prop:AC_LG}
Let $e=u_1u_2 \in E(G)$ and $\pi \in L_G$. Denote by $\hat{0}_e$ the bond whose blocks are singletons except the one block $\{u_1,u_2\}$. Then $\mu_G(\hat{0},\pi)=\mu_{G \setminus e}(\hat{0}, \pi)-\mu_{G}(\hat{0}_e, \pi)$ if $\pi \in L_{G \setminus e}$, and $\mu_G(\hat{0},\pi)=-\mu_{G}(\hat{0}_e,\pi)$ otherwise.
\end{prop} 

Let us take a bond $\pi \in L_G$. Let $G/\pi$ be the graph obtained from $G$ by contracting each block $B \in \pi$ to the vertex $v_B$, and denote by $V/\pi$ the vertex set of $G/\pi$. For $B \in \pi$, define the variable $v_{B}$ associated with the vertex $v_B$
to be
\[
v_{B}=1-\prod_{v \in B}(1-v).
\]

\begin{thm}\label{thm:AC_LG} For a graph $G=(V,E)$, its acyclic orientation polynomial $A_G(V)$ equals
\begin{equation}\label{eq:Mobius}
A_G(V)=\sum_{\pi \in L_G}(-1)^{d-|\pi|}\mu_G{(\hat{0},\pi)}\prod_{B \in \pi}{v_B}.
\end{equation}
By the M\"obius inversion formula, equation \eqref{eq:Mobius} is equivalent to
\begin{equation*}
\sum_{\pi \in L_G}(-1)^{d-|\pi|}A_{G/\pi}(V/\pi)=\prod_{v \in V}v.
\end{equation*}
\end{thm}

For a non-empty subset $U$ of $V$, define 
\[
\mathcal{R}(U)=\{\,\pi \in L_G \mid B \cap U \ne \emptyset \mbox{ for every } B \in \pi \,\},
\]
and then extracting the coefficient of $\prod_{v \in U}v$ from equation \eqref{eq:Mobius} yields
\begin{equation}\label{eq:a(G,U)}
a(G,U)=
\sum_{\pi \in \mathcal{R}(U)}
(-1)^{d-|U|}\mu_G(\hat{0}, \pi).
\end{equation}

As in \cref{cor:unique}, \cref{thm:AC_LG} gives the following corollary.
\begin{cor}[{\cite[Theorem 7.3]{GZ83}}]\label{cor:unique2} Let $G$ be a connected graph with the vertex set $V$. For any vertex $v \in V$, we have $|a(G,v)|=\mu(G)$.
\end{cor}

\cite[Theorem 7.3]{GZ83} was proved via the theory of hyperplane arrangements, and three more proofs were also presented in \cite{GS00}. We shall alternatively give a \emph{non-inductive} proof for \cref{thm:AC_LG} using \cite[Theorem 7.3]{GZ83} and Weisner's theorem.

\begin{thm}[Weisner's theorem] \label{thm:weisner}
Let $L$ be a finite lattice with at least two elements, $\mu_L(\cdot,\cdot)$ its M\"obius function, $\hat{0}_L$ its least element, and $\hat{1}_L$ its greatest element. For $a \in L$ with $a \neq \hat{1}_L$, 
\[
\sum_{t:\,t\wedge a=\hat{0}_L} \mu_L(t,\hat{1}_L) = 0,
\]
where $a\wedge b$ is the largest element $p$ satisfying $p \leq a$ and $p \leq b$.
\end{thm}

Let $G^U$ be the graph whose vertex set is $V\cup \{u_0\}$ and edge set is $E\cup \{u_0v \mid v\in U\}$. For $\mathfrak{o} \in \mathcal{A}(G^U,\{u_0\})$, deleting $u_0$ from $\mathfrak{o}$ yields an acyclic orientation whose sinks are contained in $U$. This procedure is bijective, which gives the following identity:
\[
a(G^U, u_0)=a(G, \subseteq U),
\]
where $a(G, \subseteq U)$ denotes the number of acyclic orientations of $G$ whose sinks belong to $U$.

\begin{prop} \label{prop:lattice}
For a non-empty proper subset $U$ of $V$, we have
\begin{equation*}
\sum_{\pi\in L_G} (-1)^{d-|\pi|}a(G/\pi, \subseteq U/\pi) = 0,
\end{equation*}
where $U/\pi$ is the subset of $V/\pi$ corresponding to $U$, i.e., $U/\pi = \{ v_{B} \mid B\in\pi, B\cap U \neq \emptyset\}$.
\end{prop}

From \cref{prop:lattice}, we obtain a non-inductive proof of \cref{thm:AC_LG}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{The map from $\mathcal{A}(G)$ to $L_G$}\label{sec:AC_SD}
We present an expression of $A_G(V)$ in terms of the map $\pi:\mathcal{A}(G) \to L_G$ defined in \cite[Section 4]{BN19}. Let us fix an ordering of $V$, and take $\mathfrak{o} \in \mathcal{A}(G)$.
For $j \ge 1$, suppose that $B_1, B_2, \dots, B_{j-1} \subseteq V$ are defined. Denote by $s_j$ the smallest element in $V\setminus \cup_{i=1}^{j-1} B_i$.
Let $B_j$ be the collection of vertices $v$ in $V\setminus\cup_{i=1}^{j-1} B_i$ such that there is a directed path in $\mathfrak{o}$ from $v$ to $s_j$.
Define $\pi(\mathfrak{o})=\{B_1, \cdots, B_q\}$, where $q$ is the largest integer with $B_{q} \ne \emptyset$. Clearly, $\pi(\mathfrak{o})\in L_G$. The blocks in $\pi(\mathfrak{o})$ are called the \emph{sink-components}.

Take an edge $e=u_1u_2 \in E(G)$. Let $\mathcal{A}_{\mbox{$\nleftrightarrow$}}$ be the set of acyclic orientations of $G\setminus e$ which contain neither a directed path from $u_1$ to $u_2$ nor one from $u_2$ to $u_1$. 
Define 
\[
\mathcal{A}(G)_e=\{ \mathfrak{o} \cup \overrightarrow{u_2u_1} \,\mid\,\mathfrak{o} \in \mathcal{A}_{\mbox{$\nleftrightarrow$}} \}\mbox{ and } \mathcal{A}(G)^e=\mathcal{A}(G) \setminus \mathcal{A}(G)_e.
\]
Deleting $e$ from an acyclic orientation in $\mathcal{A}(G)^e$ gives a bijection between $\mathcal{A}(G)^e$ and $\mathcal{A}(G \setminus e)$, while contracting $e$ yields a bijection between $\mathcal{A}(G)_e$ and $\mathcal{A}(G/e)$.

\begin{prop}\label{prop:AC_SC} Let $e=u_1u_2$ with $u_1 <u_2$ be the smallest edge of $E(G)$ in the lexicographic order.
Then for $\mathfrak{o}\in\mathcal{A}(G)^e$, the sink-components of $\mathfrak{o}$ are preserved when deleting $e$ from $\mathfrak{o}$. For $\mathfrak{o}\in\mathcal{A}(G)_e$, let $\pi(\mathfrak{o})=\{ B_1, B_2, \dots,B_q \}$, and let $B_1$ and $B_2$ be the sink-components containing $u_1$ and $u_2$, respectively. Then $\pi(\mathfrak{o}/e) = \{ B_1\cup B_2, B_3, \dots, B_q \}$.
\end{prop}
\begin{thm}\label{thm:AC_SD} For a graph $G=(V,E)$, its acyclic orientation polynomial $A_G(V)$ equals
\begin{equation*}
A_G(V)=\sum_{\mathfrak{o} \in \mathcal{A}(G)}\prod_{ B \in \pi(\mathfrak{o})}v_{B}.
\end{equation*}
\end{thm}

Comparing \cref{thm:AC_LG,thm:AC_SD} gives a proof for \cite[Theorem 7.4]{GZ83} whose original proof exploits \cref{cor:unique2} (\cite[Theorem 7.3]{GZ83}).
\begin{cor}[{\cite[Theorem 7.4]{GZ83}}]\label{thm:7.4} For a bond $\pi \in L_G$, the cardinality of the preimage $\{ \mathfrak{o} \in \mathcal{A}(G) \mid\pi=\pi(\mathfrak{o})\}$ is equal to $|\mu_G(\hat{0},\pi)|=(-1)^{d-|\pi|}\mu(\hat{0},\pi)$.
\end{cor}

If each element in $U \subseteq V$ is smaller than any elements in $V \setminus U$, then for $\mathfrak{o} \in \mathcal{A}(G)$, its sinks are in $U$ if and only if $\pi(\mathfrak{o})$ lies in $\mathcal{R}(U)$, which together with \cite[Theorem 7.4]{GZ83} gives
\begin{equation}\label{eq:subset}
a(G, \subseteq U) = 
\sum_{\pi \in \mathcal{R}(U)}
(-1)^{d-|\pi|}\mu_G(\hat{0}, \pi).
\end{equation}
Using the inclusion-exclusion principle, equation \eqref{eq:subset} is equivalent to equation \eqref{eq:a(G,U)}. Hence, we remark that \cref{thm:AC_LG} could be alternatively proved using \cite[Theorem 7.4]{GZ83}. 

We close this section with a generating function for $a(G, \subseteq U)$:
\[
\sum_{
U \subseteq V}\Big(a(G, \subseteq U) \prod_{v \in U}v\Big)=\sum_{\pi \in L_G}(-1)^{d-|\pi|}\mu_G(\hat{0},\pi)\prod_{B \in \pi}\Big(\prod_{v \in B}(1+v)-1\Big).
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Chromatic symmetric functions and Stanley's sink theorem}\label{sec:Stanley}
In this section, we present a \emph{new} proof for \cite[Theorem 3.3]{Stanley95}, which expresses the number of acyclic orientations with a fixed number of sinks as the sum of the coefficients of elementary symmetric functions $e_{\lambda}$ with a fixed length in the expansion of the chromatic symmetric function. Our proof does not require the theory of quasi-symmetric functions and $P$-partitions, which was used in the original proof of \cite[Theorem 3.3]{Stanley95}.

We begin with the definition of the \emph{chromatic symmetric function} $X_G$ of a graph $G$. Let $x_1,x_2, \dots$ be commuting indeterminates. A \emph{proper
coloring} $\kappa$ of $G$ is a function $\kappa:V \to \{1,2,3, \dots \}$ such that $\kappa(v) \ne \kappa(v') $ whenever $v,v' \in V$ are adjacent.
\begin{defn}[{\cite[Definition 2.1]{Stanley95}}] The \emph{chromatic symmetric function} $X_G$
is defined as
\[
X_G=\sum_{\kappa}{\prod_{v \in V}x_{\kappa(v)}},
\] 
where the sum is over all proper colorings $\kappa$ of $G$.
\end{defn}

We will expand the symmetric function $X_G$ in terms of power sum symmetric functions $p_\lambda$ and elementary symmetric functions $e_\lambda$. Note that $\{p_{\lambda} \mid \lambda    \vdash n \}$ and $ \{e_{\lambda} \mid \,\lambda\vdash n \}$ form bases for the space of all homogeneous symmetric functions of degree $n$.

Let us collect expansions of $X_G$ with respect to power sum symmetric functions $p_\lambda$:
\begin{align}
X_G &= \sum_{S \subseteq E}(-1)^{|S|}p_{\lambda(S)} &&  \mbox{{\cite[Theorem 2.5]{Stanley95}}} \label{eq:XG=sub} \\  
&= \sum_{S \in B_G}(-1)^{|S|}p_{\lambda(S)} &&  \mbox{{\cite[Theorem 2.9]{Stanley95}}} \nonumber \\ 
&= \sum_{\pi \in L_G}\mu(\hat{0},\pi)p_{{\operatorname{type}(\pi)}} && \mbox{{\cite[Theorem 2.6]{Stanley95}}} \nonumber \\ 
&= \sum_{\mathfrak{o} \in \mathcal{A}(G)}(-1)^{d-|\pi(\mathfrak{o})|}p_{{\operatorname{type}(\pi(\mathfrak{o}))}} && \mbox{{\cite[Proposition 5.2]{BN19}}},  \nonumber
\end{align}
where $\lambda(S)$ and $\operatorname{type}(\pi)$ are the non-increasing sequences of the sizes of connected components of a spanning subgraph $S$, and elements of a vertex partition $\pi$, respectively. 

Let $\Lambda$ be the $\mathbb{Q}$-algebra of symmetric functions with $\mathbb{Q}$-coefficients. Define an algebra homomorphism $\phi: \Lambda \to \mathbb{Q}[t]$ by $\phi(e_n)=t$ for each $n \geq 1$. Then
\begin{equation*}
\phi(e_{\lambda}) = t^{l(\lambda)}.
\end{equation*}
\begin{lem}[{\cite[Exercise 7.43]{Stanley99}}]\label{lem:image}
The image of $p_n$ under $\phi$ is equal to
\begin{equation*}
\phi(p_n) = (-1)^{n-1}(1-(1-t)^n).
\end{equation*}
\end{lem}

Applying \cref{lem:image} to equation \eqref{eq:XG=sub} and comparing with the expression of $a_G(t)$ in \cref{thm:AC_Sub}, we have an alternating proof of the sink theorem.
\begin{thm}[{\cite[Theorem 3.3]{Stanley95}}]\label{thm:Stanley} Let $X_G=\sum_{\lambda  \,  \vdash  \,  d}c_{\lambda}e_{\lambda}$
be the expansion of the chromatic symmetric function $X_G$ in terms of elementary symmetric functions $e_{\lambda}$ and let $\operatorname{sink}(G,j)$ be the number of acyclic orientations of $G$ with $j$
sinks. Then 
\begin{equation*}
\operatorname{sink}(G,j)=\sum_{\substack{\lambda  \, \vdash \,  d \\ l(\lambda)=j}}c_\lambda.
\end{equation*}
\end{thm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{On distinguishing graphs by acyclic orientation polynomials} \label{sec:invariant}

We end this paper with a discussion on how well graphs are distinguished by the polynomials $A_G(V)$ and $a_G(t)$. Stanley \cite{Stanley95} asked the question of whether the chromatic symmetric polynomial $X_G$ distinguishes non-isomorphic trees. The answer to the question is still unknown, but several graph polynomials \cite{GS01, MMW08} associated with $X_G$ have been introduced in the endeavor to resolve the question.

The (univariate) polynomial $a_G(t)$ is a \emph{weaker} invariant than $X_G$ by Stanley's sink theorem. Trees with $10$ or fewer vertices are distinguished by $a_G(t)$. But there exist non-isomorphic trees having the identical $a_G(t)$ with $11$ vertices. These two trees shown in \cref{fig:instances} were introduced in \cite{EG06} as the smallest instances which are not distinguished by the subtree data. 

\begin{figure}[h]
\centering
\setlength{\tabcolsep}{40pt}
    \begin{tabular}{cc}
         \begin{tikzpicture}
         %-------NODES----------------
         \fill (1,1) circle (1.5pt);
         \fill (2,1) circle (1.5pt);
         \fill (3,1) circle (1.5pt);
         \fill (4,1) circle (1.5pt);
         \fill (5,1) circle (1.5pt);
         \fill (1-0.3,0) circle (1.5pt);
         \fill (1+0.3,0) circle (1.5pt);
         \fill (2-0.3,0) circle (1.5pt);
         \fill (2+0.3,0) circle (1.5pt);
         \fill (4,0) circle (1.5pt);
         \fill (5,0) circle (1.5pt);
         %-------EDGES----------------
         \draw (1,1)--(2,1);
         \draw (2,1)--(3,1);
         \draw (3,1)--(4,1);
         \draw (4,1)--(5,1);
         
         \draw (1,1)--(1-0.3,0);
         \draw (1,1)--(1+0.3,0);
         \draw (2,1)--(2-0.3,0);
         \draw (2,1)--(2+0.3,0);
         \draw (4,1)--(4,0);
         \draw (5,1)--(5,0);
         
         \end{tikzpicture}&
         \begin{tikzpicture}
         %-------NODES----------------
         \fill (1,1) circle (1.5pt);
         \fill (2,1) circle (1.5pt);
         \fill (3,1) circle (1.5pt);
         \fill (4,1) circle (1.5pt);
         \fill (5,1) circle (1.5pt);
         \fill (1-0.3,0) circle (1.5pt);
         \fill (1+0.3,0) circle (1.5pt);
         \fill (3,0) circle (1.5pt);
         \fill (4-0.3,0) circle (1.5pt);
         \fill (4+0.3,0) circle (1.5pt);
         \fill (5,0) circle (1.5pt);
         %-------EDGES----------------
         \draw (1,1)--(2,1);
         \draw (2,1)--(3,1);
         \draw (3,1)--(4,1);
         \draw (4,1)--(5,1);
         
         \draw (1,1)--(1-0.3,0);
         \draw (1,1)--(1+0.3,0);
         \draw (3,1)--(3,0);
         \draw (4,1)--(4-0.3,0);
         \draw (4,1)--(4+0.3,0);
         \draw (5,1)--(5,0);

         \end{tikzpicture}
    \end{tabular}
    \caption{Two non-isomorphic trees with the same $a_G(t)$.} 
\label{fig:instances}  
\end{figure}

The (multivariate) acyclic orientation polynomial $A_G(V)$ is a \emph{complete} isomorphism invariant. To see this, we first assume that $G$ is connected. For two vertices $u_1,u_2 \in V$, the coefficient of $u_1u_2$ in $A_G(V)$ is zero if and only if $u_1$ and $u_2$ are adjacent. Hence, the polynomial $A_G(V)$ can recover the original graph $G$. For any graph $G$, the polynomial $A_G(V)$ has a factorization into those of its connected components, and therefore using the previous argument applied to each component shows that $G$ can be determined by $A_G(V)$.


\acknowledgments{
The authors would like to thank Jang Soo Kim, Bruce Sagan, and Thomas Zaslavsky for helpful comments and corrections.
}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
