%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{40}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
% \usepackage{mathrsfs}
% \usepackage{enumitem}
% \usepackage{stmaryrd}
% \usepackage{shuffle}
% \usepackage{multicol} %multiple columns
% \usepackage{mathtools}
% \usepackage{commath}%for \abs
\usepackage{caption}
\usepackage{subcaption}



\usepackage{tikz}
\usetikzlibrary{calc,fit,shapes,positioning}
%vertex and edge styles
\tikzstyle{vertex} = [circle,draw=black,minimum size=2pt,inner sep=1pt] %for vertices with label
\tikzstyle{vertexSmall} = [circle,draw=black,minimum size=2pt,fill=white] %for vertices without label
\tikzstyle{edge} = [line width=1pt] %for undirected edges
\tikzstyle{arrow} = [edge,->] %for directed edges
\tikzstyle{descent} = [red,dashed,line width=2pt,->] %use for descent edges

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\P}{\mathbb{P}}

\newcommand{\qand}{\quad \text{and}\quad}
\newcommand{\vect}{\vec}
\newcommand{\lp}{\left(}
\newcommand{\rp}{\right)}
\newcommand{\lb}{\left[}
\newcommand{\rb}{\right]}
\newcommand{\lc}{\left\{}
\newcommand{\rc}{\right\}}
\newcommand{\lab}{\left|}
\newcommand{\rab}{\right|}
\newcommand{\sm}{\setminus}
\DeclareMathOperator{\im}{im}
\DeclareMathOperator{\curl}{curl}
\DeclareMathOperator{\diver}{div}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Ht}{ht}
\DeclareMathOperator{\Wt}{wt}
\newcommand{\ra}{\rightarrow}
\renewcommand{\Re}{\mathbb{R}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\sB}{\mathcal{B}}
\newcommand{\sM}{\mathcal{M}}
\newcommand{\sF}{\mathcal{F}}
\DeclareRobustCommand*{\ora}{\overrightarrow}  %%% Use me for A(D,k)
\DeclareRobustCommand*{\ola}{\overleftarrow}  %%% Use me for A(D,k)
\renewcommand{\phi}{\varphi}
\newcommand{\eps}{\varepsilon}
\DeclareMathOperator{\Real}{Re}
\DeclareMathOperator{\Imag}{Im}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\asc}{asc}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\Inv}{INV}
\DeclareMathOperator{\INV}{INV}
\DeclareMathOperator{\Des}{DES}
\DeclareMathOperator{\DES}{DES}
\DeclareMathOperator{\fix}{fix} %fixed points for involutions
\DeclareMathOperator{\Hess}{Hess}
\usepackage{hyperref}
%\hypersetup{
%  colorlinks   = true, %Colours links instead of ugly boxes
%  urlcolor     = black, %Colour for external hyperlinks
%  linkcolor    = blue, %Colour of internal links
%  citecolor   = green %Colour of citations
%} %Temporarily changing the color to green so as not to confuse with any of our comment colors
\usepackage{cleveref}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{question}[theorem]{Question}
\newtheorem{prob}[theorem]{Problem}

\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}



\newcommand{\A}{A}
\renewcommand{\a}{a}
\renewcommand{\SS}[1]{\textcolor{red}{#1}}
\newcommand{\KC}[1]{\textcolor{violet}{#1}}
\newcommand{\NS}[1]{\textcolor{cyan}{#1}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\qbinom}[3]{\begin{bmatrix}
		#1\\ #2
	\end{bmatrix}_{#3}}
\newcommand{\sig}{\sigma}
\newcommand{\sub}{\subseteq}

\DeclareMathOperator{\odd}{odd}
\DeclareMathOperator{\mult}{mult}
\DeclareMathOperator{\rev}{rev}
\newcommand{\bone}{\mathbf{1}} 
\newcommand{\X}{\widetilde{X}}
\newcommand{\maj}{\mathrm{maj}}

\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{lipsum}

%% define your title in the usual way
%\title[Optional shorter title]{Something to do with math}
\title{Eulerian Polynomials for Digraphs}
%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
% \author[Optional shorter names]{Longer names me. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}
\author{Kyle Celano\thanks{\href{mailto:celanok@wfu.edu}{celanok@wfu.edu}}\addressmark{1}, Nicholas Sieger\thanks{\href{mailto:nsieger@ucsd.edu}{nsieger@ucsd.edu}}\addressmark{2}, \and Sam Spiro\thanks{\href{mailto:sas703@scarletmail.rutgers.edu}{sas703@scarletmail.rutgers.edu}. This material is based upon work supported by the National Science Foundation Mathematical Sciences Postdoctoral Research Fellowship under Grant No. DMS-2202730.}\addressmark{3}} 

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Dept.\ of Mathematics, Wake Forest University  \\ \addressmark{2}Dept.\ of Mathematics, University of California San Diego\\ \addressmark{3}Dept.\ of Mathematics, Rutgers University}

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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
%\abstract{\lipsum[1]}
\abstract{
   Given an $n$-vertex digraph $D$ and a labeling $\sigma:V(D)\to [n]$, we say that an arc $u\to v$ of $D$ is a descent of $\sigma$ if $\sigma(u)>\sigma(v)$.   Foata and Zeilberger introduced a generating function $A_D(t)$ for labelings of $D$ weighted by descents, which simultaneously generalizes both Eulerian polynomials and Mahonian polynomials.  Motivated by work of Kalai, we look at problems related to $-1$ evaluations of $A_D(t)$.  In particular, we give a combinatorial interpretation of $|A_D(-1)|$ in terms of ``generalized alternating permutations'' whenever the underlying graph of $D$ is bipartite.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Eulerian polynomial, alternating permutations, combinatorial reciprocity}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{sample.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above





\section{Introduction}
Descents and inversions are two of the oldest and most well-studied \textit{permutation statistics} dating back to work of MacMahon 
\cite{macmahon2001combinatory,macmahon1913indices}. A \textit{descent} of a permutation $\sigma\in \mathfrak{S}_n$ on the set $[n]:=\{1,2,\dots,n\}$ is an index $i\in [n-1]$ such that $\sigma(i)>\sigma(i+1)$, and an inversion is a pair  of integers $(i,j)$ with $1\leq i<j\leq n$ such that $\sigma(i)>\sigma(j)$. The number of descents and inversions of $\sigma$ are denoted by $\des(\sigma)$ and $\inv(\sigma)$, respectively.

% For example, if $\sigma=23154$ (written in \textit{one-line notation}, meaning $\sigma(1)=2,\ \sigma(2)=3\dots$), then $2$ and $4$ are descents whereas $(1,3),(2,3),(4,5)$ are inversions, so $\des(\sigma)=2$ and $\inv(\sigma)=3$.

The generating functions 
\[A_n(t)=\sum_{\sigma\in \mathfrak{S}_n}t^{\des(\sigma)}\quad M_n(t)=\sum_{\sigma\in \mathfrak{S}_n}t^{\inv(\sigma)}\]
are called the \textit{Eulerian} and \textit{Mahonian} polynomials respectively. Both of these polynomials are important objects of study in many branches of combinatorics and have been generalized in many different ways.  In this paper, we consider a polynomial due to Foata and Zeilberger~\cite{FOATA199679} which generalizes both the Eulerian and Mahonian polynomials via directed graphs.


% A \textit{directed graph} or \textit{digraph} is a pair $D=(V,E)$ consisting of a finite set $V$ of \textit{vertices} and a subset $E\subset V\times V$ of \textit{(directed) edges} or \textit{arcs}. We will sometimes denote arcs $(u,v)\in E$ by $u\to v$ or even $uv$ where convenient. We further assume that $D$ has no loops i.e. no arcs of the form $(v,v)$. We do not allow multiple directed edges from one vertex to another, though it is easy to adapt our forthcoming definitions to accommodate this.

A \textit{permutation} of an $n$-vertex digraph $D=(V,E)$ is a bijection $\sigma:V\to [n]$. We will use the notation $\mathfrak{S}_D,\ \mathfrak{S}_V$, or $\mathfrak{S}_n$ to denote the set of permutations of $D$.  For a given directed graph $D=(V,E)$ and a permutation $\sigma$ of $D$, a \textit{$D$-descent} (or just \textit{descent} when $D$ is understood) is an arc $u\to v$ such that $\sigma(u)>\sigma(v)$. The total number of $D$-descents of a permutation $\sigma$ is denoted by $\des_D(\sigma)$; see \Cref{fig:basic example} for an example.

\begin{figure}[h]
	\centering
	\begin{subfigure}[b]{.5\textwidth}
		\centering
		\begin{tikzpicture}
			\node[vertex] (a) at (0,0) {$3$} ;
			\node[vertex] (b) at (1.2,1) {$4$} ;
			\node[vertex] (c) at (1.2,-1) {$1$} ;
			\node[vertex] (d) at (-1.2,1) {$5$} ;
			\node[vertex] (e) at (-1.2,-1) {$2$} ;
			
			\draw[arrow] (a) --(b);
			\draw[descent] (b) edge[bend left] (c);
			\draw[arrow] (c) edge[bend left] (b);
			\draw[descent] (a)--(c);
			\draw[arrow] (a)--(d);
			\draw[descent] (d) -- (e);
			\draw[arrow] (e) -- (a);
			
		\end{tikzpicture} 
	\end{subfigure}   
	~
	\begin{subfigure}[b]{.4\textwidth}
		\centering
		\begin{tikzpicture}
			\node[vertex] (a) at (0,0) {$5$} ;
			\node[vertex] (b) at (1.2,1) {$1$} ;
			\node[vertex] (c) at (1.2,-1) {$2$} ;
			\node[vertex] (d) at (-1.2,1) {$3$} ;
			\node[vertex] (e) at (-1.2,-1) {$4$} ;
			
			\draw[descent] (a) --(b);
			\draw[arrow] (b) edge[bend left] (c);
			\draw[descent] (c) edge[bend left] (b);
			\draw[descent] (a)--(c);
			\draw[descent] (a)--(d);
			\draw[arrow] (d) -- (e);
			\draw[arrow] (e) -- (a);
		
			
		\end{tikzpicture}
		\label{fig:basic example with digon}    
	\end{subfigure}  
	\caption{Two labelings $\pi:V(D)\to [5]$ where descent arcs are marked by red dashed lines.}
	\label{fig:basic example}
\end{figure}

% \begin{remark}\label{eg:classic}We claim that the statistic $\des_D$ generalizes both $\des$ and $\inv$.  To see this, let $\ora{P}_n$ be the digraph with vertex set $[n]$ and with arcs $(i,i+1)$ for $i\in [n-1]$, and let $\ora{K}_n$ be the digraph with vertex set $[n]$ and with arcs $(i,j)$ for integers $1\leq i<j\leq n$. The reader can check that a \textit{$\ora{P}_n$-descent} is a \textit{descent} (in the classical meaning) and a \textit{$\ora{K}_n$-descent} is an inversion, and hence
% \[\des_{\ora{P}_n}(\sigma)=\des(\sigma)\quad \des_{\ora{K}_n}(\sigma)=\inv(\sigma).\]
% See \Cref{fig: desD is desinv} for an example.
% \end{remark}
These statistics generalize both of $\des$ and $\inv$ as \Cref{fig: desD is desinv} shows.

\begin{figure}[h]
    \centering
    \begin{subfigure}[b]{.4\textwidth}   
    \centering
    \begin{tikzpicture}

        \node[vertex] (a) at (0,0) {$2$} ;
        \node[vertex] (b) at (1,0) {$3$} ;
        \node[vertex] (c) at (2,0) {$1$} ;
        \node[vertex] (d) at (3,0) {$5$} ;
        \node[vertex] (e) at (4,0) {$4$} ;

        \draw[arrow] (a) --(b);
        \draw[descent] (b)--(c);
        \draw[arrow] (c)--(d);
        \draw[descent] (d) -- (e);

        
    \end{tikzpicture}
    \caption{ $\des(23154)=2$ }
    \label{fig:des Pn is des}    
    \end{subfigure}
    \begin{subfigure}[b]{.4\textwidth}
    \centering
    \begin{tikzpicture}
        \node[vertex] (a) at (0,0) {$2$} ;
        \node[vertex] (b) at (1,0) {$3$} ;
        \node[vertex] (c) at (2,0) {$1$} ;
        \node[vertex] (d) at (3,0) {$5$} ;
        \node[vertex] (e) at (4,0) {$4$} ;

        \draw[arrow] (a) --(b);
        \draw[descent] (a) edge[bend left] (c);
        \draw[arrow] (a) edge[bend left=45] (d);
        \draw[arrow] (a) edge[bend left=60] (e);
        \draw[descent] (b)--(c);
        \draw[arrow] (b) edge[bend left] (d);
        \draw[arrow] (b) edge[bend left=45] (e);
        \draw[arrow] (c)--(d);
        \draw[arrow] (c) edge[bend left] (e);
        \draw[descent] (d) -- (e);
        
    \end{tikzpicture}
    \caption{ $\inv(23154)=3$ }
    \label{fig:des Kn is inv}    
    \end{subfigure}    
    \caption{The Eulerian polynomial  $\A_D(t)$ generalizes both descents and inversions.}
    \label{fig: desD is desinv}
\end{figure}
With all this in mind, we can now define the central object of study for this paper: the \textit{Eulerian polynomial} of a digraph $D=(V,E)$ is the generating function
\begin{equation}
    A_D(t)=\sum_{\sigma\in \mathfrak{S}_D}t^{\des_D(\sigma)}.
\end{equation}
In particular, we have $A_{\ora{P_n}}(t)=A_n(t)$ and $A_{\ora{K_n}}(t)=M_n(t)$. 

This polynomial can be seen in other work: as a \textit{weighted-inversion} generating function as in \cite{KADELL198522,DEGENHARDT200049}; as an  \textit{Eulerian polynomial for a (particular) family $\mathfrak{B}_n$ of digraphs} \cite{ARCHER2020112041}; as a specialization of the \textit{chromatic quasisymmetric function for digraph} \cite{Ellzey_2017} and \textit{$B$-polynomial} \cite{awan_bernardi_2020}. There are also a myriad of other objects generalizing Eulerian polynomials which are related by varying degrees to ours.

% We begin by establishing a list of elementary properties for $\A_D(t)$, some of which were established by Even-Zohar \cite{Even-Zohar2017}. For this, we recall that a polynomial $f(t)=\sum_{k} a(k) t^k$ is \textit{palindromic with center $d/2$} if $a(k)=a(d-k)$ for all $k$. 

% \begin{prop}\label{prop basic facts}
%     Let $D=(V,E)$ be a directed graph with $n$ vertices and $m$ arcs.
%      \begin{enumerate}
%         \item[(a)] The polynomial $\A_D(t)$ is palindromic with center $m/2$.
%         \item[(b)] If $(u,v),(v,u)\in E$, then $\A_D(t)=t\cdot \A_{D-(u,v)-(v,u)}(t)$.
%         \item[(c)] If $D=\bigsqcup_{i=1}^r D_i$ is a disjoint union of digraphs of orders $n_1,\ldots,n_r$, then
%         \[\A_D(t)=\binom{n}{n_1,\ldots,n_r} \cdot \prod_{i=1}^r A_{D_i}(t).\]
%         \item[(d)] If $D$ is formed by taking the disjoint union of digraphs $D_1,\ldots,D_r$ of orders $n_1,\ldots,n_r$ and then adding all arcs of the form $u\to v$ with $u\in V_i,\ v\in V_j$ and with $i<j$, then
%         \[\A_D(t)=\begin{bmatrix} n\\ n_1,\ldots,n_r\end{bmatrix}_t \cdot \prod_{i=1}^r A_{D_i}(t).\]
%     \end{enumerate}
% \end{prop}
%     We note that (b) and (c) allows us to reduce our problems to studying digraphs $D$ which are orientations of connected graphs. 



% Next, we have a lemma which allows us to express the Eulerian polynomial of a digraph $D$ in terms of Eulerian polynomials of induced subgraphs of $D$. 
%  \begin{lemma}\label{lemma split into subgraphs}
%      If $D=(V,E)$ is an $n$-vertex digraph and $k\in [n]$, then
%      \[
%          \A_D(t) = \sum_{S\in \binom{V}{k}} \frac{t^{e_D(S,\overline{S})} + t^{e_D(\overline{S},S)}}{2}\A_{D[S]}(t)\A_{D - S}(t).
%      \]
%  \end{lemma}
 

The primary objective of this extended abstract is to study evaluations of $A_D(t)$ at $-1$. See \cite{celano2023eulerian} for the full paper. This is a problem in the area of \textit{combinatorial reciprocity}, which studies combinatorial polynomials evaluated at negative integers.  For example, the classical Eulerian and Mahonian polynomials both have good combinatorial interpretations for their evaluation at $-1$: the former being the number of \textit{alternating permutations} \cite{foata2005theorie} and the latter being the number of \textit{correct proofs of the Riemann hypothesis}\footnote{As of the time of writing.}. Many more results on combinatorial reciprocity can be found in the book by Beck and Sanyal~\cite{beck2018combinatorial}.

%a well known result of Stanley~\cite{stanley1973acyclic} says that the chromatic polynomial of a graph $G$ evaluated at $-1$ is equal (up to sign) to the number of acyclic orientations of $G$. Similarly
%, and more on alternating permutations can be found in the survey by Stanley \cite{stanley2009survey}.

Kalai~\cite[Section 8.1]{KALAI2002412} makes a critical observation about $A_D(-1)$.
\begin{prop}\label{prop:negOne}
    If $D,D'$ are orientations of the same graph $G$, then $|\A_D(-1)|=|\A_{D'}(-1)|$.
\end{prop}
% This result follows from the fact that if any arc of $D$ is reversed, then the number of descents for any permutation $\sig\in \mathfrak{S}_V$ changes by exactly 1. 
With \Cref{prop:negOne} in mind, for any graph $G$ we can define
\[\nu(G):=|\A_D(-1)|,\]
where $D$ is any orientation of $G$.  The problem of studying $\nu(G)$ was first introduced by Kalai \cite{KALAI2002412} due to its relation with the Condorcet paradox in social choice theory, and a few basic properties of $\nu(G)$ were established by Even-Zohar \cite{Even-Zohar2017}.  Outside of this, nothing seems to be known about $\nu(G)$ despite Kalai raising the problem over 20 years ago.

In this extended abstract, we prove three types of results related to $\nu(G)$: we give combinatorial interpretations for $\nu(G)$ for a large class of graphs $G$, we determine the maximum and minimum values achieved by $\nu(G)$ amongst $n$ vertex trees, and we consider the refined problem of determining the multiplicity of $-1$ as a root of $\A_D(t)$. 

\section{Combinatorial Interpretations for \texorpdfstring{$\nu(G)$}{}}
% A key observation towards understanding $\nu(G)$ is a result of Foata and Sch\"utzenberger~\cite{foata2005theorie} (see also \cite[Exercise 135]{stanley_2011}) which states that the Eulerian polynomial $A_n(t)$ evaluated at $t=-1$ is equal (up to sign) to the number of alternating permutations of size $n$, i.e.\ the number of permutations $\sig$ with $n$ odd and $\sig(1)<\sig(2)>\sig(3)<\cdots >\sig(n)$.  Because $A_n(t)=A_{\ora{P}_n}(t)$ for $\ora{P}_n$ the directed path, this result implies $\nu(P_n)$ is equal to the number of alternating permutations of size $n$. 

A classical result of Foata and Sch\"utzenberger~\cite{foata2005theorie} (see also \cite[Exercise 135]{stanley_2011}) states that for odd $n$ the Eulerian polynomial $A_n(t)$ evaluated at $t=-1$ is equal (up to sign) to the number of \textit{alternating permutations} of length $n$, i.e.\ the number of permutations $\sig$ and $\sig(1)<\sig(2)>\sig(3)<\cdots >\sig(n)$.  Because $A_n(t)=A_{\ora{P}_n}(t)$ for $\ora{P}_n$ the directed path, this result implies $\nu(P_n)$ is equal to the number of alternating permutations of size $n$. 

Given this observation, it is natural to expect $\nu(G)$ to count ``alternating permutations for graphs'' for some generalized notion of alternating permutations.  There are many such generalizations one could consider, for example, one could force every maximal path of $G$ to be an alternating permutation.  However, it turns out that the definition we will want to consider is the following (non-obvious) generalization.


\begin{definition}
    Given an $n$-vertex graph $G$, we say that an ordering $\pi=(\pi_1,\ldots,\pi_n)$ of the vertex set $V(G)$ is an \textit{even sequence} if each of the subgraphs $G[\pi_1,\ldots,\pi_i]$ induced by the first $i$ vertices of $\pi$ have an even number of edges for all $1\le i\le n$.  We let $\eta(G)$ denote the number of even sequences of $G$. 
\end{definition}


\begin{figure}[h]
    \centering
    \begin{tikzpicture}
        \coordinate (base1) at (-5,3);
        \coordinate (base2) at (0,3);
        \coordinate (base3) at (5,3);
        \coordinate (base4) at (-3,0);
        \coordinate (base5) at (3,0);

        \coordinate (p1) at (-2,0);
        \coordinate (p2) at (-1,0);
        \coordinate (p3) at (0,0);
        \coordinate (p4) at (1,0);
        \coordinate (p5) at (2,0);
        \coordinate (label) at (0,-1);
        
        %P_5[3]
        \node[vertex] (13) at ($(base1) + (p3)$) {$3$};
        \node[draw,line width=1pt] at($(base1) + (p3) + (label)$) {$P_5[3]$};

        %P_5[3,1]
        \node[vertex] (23) at ($(base2) + (p3)$) {$3$};
        \node[vertex] (21) at ($(base2) + (p1)$) {$1$};
        \node[draw,line width=1pt] at($(base2) + 0.5*(p1) + 0.5*(p3) + (label)$) {$P_5[3,1]$};
        
        %P_5[3,1,2]
        \node[vertex] (33) at ($(base3) + (p3)$) {$3$};
        \node[vertex] (31) at ($(base3) + (p1)$) {$1$};
        \node[vertex] (32) at ($(base3) + (p2)$) {$2$};
        \draw[edge] (33) --(32) --(31);
        
        \node[draw,line width=1pt] at($(base3) + (p2) + (label)$) {$P_5[3,1,2]$};

        %P_5[3,1,2,4]
        \node[vertex] (43) at ($(base4) + (p3)$) {$3$};
        \node[vertex] (41) at ($(base4) + (p1)$) {$1$};
        \node[vertex] (42) at ($(base4) + (p2)$) {$2$};
        \node[vertex] (44) at ($(base4) + (p5)$) {$5$};
        \draw[edge] (43) --(42) --(41);
        
        \node[draw,line width=1pt] at($(base4) + 0.5*(p1) + 0.5*(p5) + (label)$) {$P_5[3,1,2,5]$};

        %P_5[3,1,2,4,5]
        \node[vertex] (53) at ($(base5) + (p3)$) {$3$};
        \node[vertex] (51) at ($(base5) + (p1)$) {$1$};
        \node[vertex] (52) at ($(base5) + (p2)$) {$2$};
        \node[vertex] (54) at ($(base5) + (p4)$) {$4$};
        \node[vertex] (55) at ($(base5) + (p5)$) {$5$};
        \draw[edge] (55) -- (54) -- (53) --(52) --(51);
        
        \node[draw,line width=1pt] at($(base5) + (label)$) {$P_5[3,1,2,5,4]$};
    \end{tikzpicture}

    \caption{A depiction of the induced subgraphs $P_5[\pi_1,\ldots,\pi_i]$ for the ordering $\pi=(3,1,2,5,4)$ of the path graph $P_5$.  Note that $\pi$ is an even sequence since each of these induced subgraphs have an even number of edges.  We also observe that $\pi^{-1}=(2,3,1,5,4)$ is an alternating permutation.} 
    \label{fig:evenEg}
\end{figure}

\begin{lemma}\label{lem:etaRecurrence}
    For any graph $G$, 
    \begin{enumerate}
        \item[(a)] $\nu(G)\leq \sum_{v\in V(G)} \nu(G-v)$.
        \item[(b)] If $G$ has an odd number of edges, $\eta(G)=0.$ Otherwise, $\eta(G)=\sum_{v\in V(G)}\eta(G-v).$
        \item[(c)] $\nu(G)\leq \eta(G)$.
    \end{enumerate}
\end{lemma}
One can verify that even sequences for the path graph $P_n$ with vertex set $[n]$ are exactly inverses of alternating permutations of size $n$, so $\nu(P_n)=\eta(P_n)$ in this case. Our main result shows that this equality holds for a substantially larger class of graphs.  

To state this result, we remind the reader that a graph is \textit{complete multipartite} if one can partition its vertices into sets $V_1,\ldots,V_r$ such that $u$ and $v$ are adjacent if and only if $u\in V_i,v\in V_j$ for some $i\ne j$.  We say that a graph is a \textit{blowup of a cycle} if one can partition its vertices into sets $V_1,\ldots,V_r$ such that $u$ and $v$ are adjacent if and only if $u\in V_i$ and $v\in V_{i+1}$ for some $i$ (with the indices written mod $r$).
\begin{theorem}\label{thm:nuEta}
    If $G$ is a graph which is either bipartite, complete multipartite, or a blowup of a cycle, then $\nu(G)=\eta(G)$.
\end{theorem}


The proofs for each of these cases follows the same basic strategy: We first show that for some ``natural'' orientation $D$ of $G$, we can easily predict the sign of $\A_D(-1)$.  From this we deduce $\nu(G)=\sum \nu(G-v)$, and hence that $\nu(G)=\eta(G)$ since the statistics $\nu,\eta$ satisfy the same recurrence relation. Accordingly, we will only discuss the proof for bipartite graphs in this extended abstract, leaving the other classes of graphs for the full paper.

% We begin with the following ``natural'' orientations for bipartite graphs.

\begin{lemma}\label{lem:bipartiteOrientation}
    Let $D$ be a digraph such that one can partition its vertex set into $U\cup V$ such that every arc $u\to v$ of $D$ has $u\in U$ and $v\in V$. Then
    \[\A_D(-1)\ge 0,\]
    and if $D$ has an even number of arcs, then
    \[\A_D(-1)=\sum_{v\in V(D)}\A_{D-v}(-1).\]
\end{lemma}

\begin{cor}\label{cor:nuBipartite}
    If $G$ is a bipartite graph with an odd number of edges, then $\nu(G)=0$, and otherwise $\nu(G)=\sum_v \nu(G-v)$.
\end{cor}

\begin{proof}[Proof of \Cref{thm:nuEta}]
    We aim to show that $\nu(G)=\eta(G)$ whenever $G$ is bipartite, complete multipartite, or a blowup of a cycle.  We first consider the case that $G$ is bipartite.  We prove this result by induction on $|V(G)|$, the base case $\nu(K_1)=\eta(K_1)=1$ being trivial.    By \Cref{cor:nuBipartite} and \Cref{lem:etaRecurrence}, if $G$ has an odd number of edges then $\nu(G)=\eta(G)=0$, and otherwise
    \[\nu(G)=\sum_{v\in V(G)} \nu(G-v)=\sum_{v\in V(G)} \eta(G-v)=\eta(G),\]
    where the middle equality used the inductive hypothesis (and that $G-v$ is bipartite whenever $G$ is).  
\end{proof}

It is tempting to try to generalize this approach by finding ``natural'' orientations of other graphs in order to show $\nu(G)=\sum \nu(G-v)$; see for example \Cref{conj:Eulerian}.  However, the following theorem shows that the inductive proof of \Cref{thm:nuEta} can not be extended beyond the class of graphs which are bipartite, complete multipartite, or blowups of cycles.


% While the above shows $\nu(G)=\eta(G)$ for a large class of graphs $G$, equality does not hold in general.  In fact, the following result shows that the family of graphs from \Cref{thm:nuEta} is essentially the largest hereditary family of graphs for which equality holds.
\begin{theorem}\label{thm:induced}
    If $G$ is a connected graph such that $\nu(G')=\eta(G')$ for all induced subgraphs $G'\sub G$, then $G$ is either bipartite, complete multipartite, or a blowup of a cycle.
\end{theorem}

Our proof of \Cref{thm:induced} relies on a structural graph theory result which may be of independent interest. The \textit{odd pan graph} $C_{2k+1}^*$ is defined to be the graph obtained by taking the odd cycle $C_{2k+1}$ and then adding a new vertex $u$ adjacent to exactly one vertex of $C_{2k+1}$. 
%; see \Cref{fig: c7star}
We say that a graph $G$ is \textit{odd pan-free} if it contains no induced subgraph which is isomorphic to $C_{2k+1}^*$ for any $k\ge 1$.

\begin{prop}\label{prop:structure}
    If $G$ is a connected graph, then $G$ is odd pan-free if and only if it is either bipartite, complete multipartite, or a blowup of a cycle.
\end{prop}

While we do not have a full understanding of $\nu(G)$ for arbitrary graphs, we are able to prove several other results regarding $\nu(G)$, such as the general bound $\nu(G)\le \eta(G)$ in the full paper. 

\section{Upper and lower bounds of \texorpdfstring{$\nu(G)$}{} and \texorpdfstring{$\eta(G)$}{}}
We next turn to the extremal problem of studying the largest and smallest possible values of $\nu(G)$ and $\eta(G)$. For arbitrary $n$-vertex graphs this is an uninteresting problem, since  $\nu(\overline{K_n})=\eta(\overline{K_n})=n!$ and $\nu(K_n)=\eta(K_n)=0$ for $n\ge 2$  are easily seen to achieve the maximum and minimum possible values.  However, this problem becomes non-trivial when one looks at smaller classes of graphs.  To this end, we consider these extremal problems for trees.

To state our result, we recall that a tree is a \textit{star} $K_{1,n}$ if there is a single-non leaf vertex; see \Cref{fig: the star}.  We say that a tree is a  \textit{hairbrush} if it consists of a path $v_0v_1\cdots v_n$ such that each vertex $v_i$ with $i\ge 1$ is adjacent to a leaf $u_i$; see \Cref{fig: the hairbrush c2}.
\begin{figure}[h]
    \centering
\begin{subfigure}[a]{.4\textwidth}
    \centering
    \begin{tikzpicture}
    \node[vertex] (v0) at (0,1) {$v_0$};
    \node[vertex] (v1) at (-2.5,0) {$v_1$};
    \node[vertex] (v2) at (-1.5,0) {$v_2$};
    \node[vertex] (v3) at (-0.5,0) {$v_3$};
    \node[vertex] (v4) at (0.5,0) {$v_4$};
    \node[vertex] (v5) at (1.5,0) {$v_5$};
    \node[vertex] (v6) at (2.5,0) {$v_6$};
    \draw[edge] (v0)--(v1);
    \draw[edge] (v0)--(v2);
    \draw[edge] (v0)--(v3);
    \draw[edge] (v0)--(v4);
    \draw[edge] (v0)--(v5);
    \draw[edge] (v0)--(v6);
    \end{tikzpicture}
    \caption{The star $K_{1,6}$}
    \label{fig: the star}
\end{subfigure}
\begin{subfigure}[a]{.4\textwidth}
    \centering
    \begin{tikzpicture}
    \node[vertex] (v0) at (0,0) {$v_0$};
    \node[vertex] (v1) at (1,0) {$v_1$};
    \node[vertex] (v2) at (2,0) {$v_2$};
    \node[vertex] (v3) at (3,0) {$v_3$};
    \node[vertex] (u1) at (1,-1) {$u_1$};
    \node[vertex] (u2) at (2,-1) {$u_2$};
    \node[vertex] (u3) at (3,-1) {$u_3$};
    \draw[edge] (v0)--(v1)--(v2)--(v3);
    \draw[edge] (v1)--(u1);
    \draw[edge] (v2)--(u2);
    \draw[edge] (v3)--(u3);
    \end{tikzpicture}
    \caption{The hairbrush $H_3$}
    \label{fig: the hairbrush c2}
\end{subfigure}

    \label{fig:extremal trees}
\end{figure}


\begin{theorem}\label{thm:etaTree}
    If $T$ is a tree on $2n+1$ vertices, then
    \[n! 2^n\le \nu(T)=\eta(T)\le (2n)!\]
    Moreover, equality holds in the lower bound if and only if $T$ is a hairbrush, and equality holds in the upper bound if and only if $T$ is a star.
\end{theorem}

To aid with our proofs, given a tree $T$, we define 
\[\X(T)=\{x\in V(T):\textrm{each component of }T-x\textrm{ has an even number of edges}\},\]
and we will denote this simply by $\X$ whenever $T$ is understood.  Our motivation for this definition is the following.
\begin{lemma}\label{cor:treeInductiveHypothesis}
    If $T$ is a tree with an even number of edges, then
    \[\nu(T)=\sum_{x\in \X} \nu(T-x).\]
\end{lemma}
With this lemma in mind, the idea for the proofs of the upper and lower bounds is as follows: we first apply \Cref{cor:treeInductiveHypothesis} and then  use induction to bound each of the terms $\nu(T-x)$ in the sum. Finally, we bound our total sum in terms of  $|\X|$ and show that equality can only occur when $|\X|=1$. In particular, we can show that 

\begin{equation}\label{eq:oneX} n!2^n\leq \nu(T-x)\leq \frac{1}{2|\widetilde{X}|-1}(2n)!\end{equation}
for all trees with an even number of edges and $x\in \tilde{X}$ and so the result follows.

\begin{remark}Our proofs yield slightly stronger bounds on $\nu(T)$ whenever $\X$ is large.   For example, \eqref{eq:oneX} gives the lower bound $\nu(T)\ge |\X| n! 2^n$.  Bounds of this form are known as  \textit{stability results} in extremal graph theory, which roughly are results saying that bounds for a graph $T$ can be substantially improved if $T$ is ``far'' from a unique extremal construction. Here, $T$ being ``far'' from $H_n$ and $K_{1,2n}$ is measured by having $|\X|$ large. 
\end{remark}

% Note that the equality $\nu(T)=\eta(T)$ follows from \Cref{thm:nuEta}, and that $\nu(T)=\eta(T)=0$ if $T$ has an even number of vertices (since $e(T)$ is odd), which is why \Cref{thm:etaTree} only considers trees with an odd number of vertices.

%As a point of comparison, the number of alternating permutations of size $2n+1$, which is equal to $\eta(P_{2n+1})=\nu(P_{2n+1})$, is known to be asymptotic to $2(2/\pi)^{2n+2} (2n+1)!$ \cite{flajolet2009analytic}.  This lies comfortably between the two extremes of \Cref{thm:etaTree}, though it is significantly closer to the upper bound.

 \section{Multiplicity of Roots}
Lastly, we consider the problem of determining the multiplicity of $-1$ as a root of $A_D(t)$, and we denote this quantity by $\mult(A_D(t),-1)$.  
% Note that studying $\mult(A_D(t),-1)$ is related to studying $\nu(G)=|A_D(-1)|$ in the sense that a graph $G$ has $\nu(G)=0$ if and only if $\mult(A_D(t),-1)>0$ for every orientation $D$ of $G$

One of the first questions one might ask in this setting is how large $\mult(A_D(t),-1)$ can be amongst all $n$-vertex digraphs?  Trivially, $\mult(A_D(t),-1)\le e(D)$ (since the degree of $A_D(t)$ is at most $e(D)$), which implies $\mult(A_D(t),-1)\le \binom{n}{2}$ if $D$ has $n$ vertices.  We prove a substantially stronger  upper bound which turns out to be sharp.
\begin{theorem}\label{thm root multiplicity upper bound}
    If $D$ is an $n$-vertex digraph, then \[\mult(A_D(t),-1)\le n-s_2(n),\] where $s_2(n)$ denotes the number of 1's in the binary expansion of $n$.  Moreover, for all $n$, there exist $n$-vertex digraphs $D$ with $\mult(\A_D(t),-1) = n - s_2(n)$.%$A_D(t)=\frac{n!}{2^{n-s_2(n)}}(1+t)^{n-s_2(n)}$.
\end{theorem}

The upper bound can be achieved with the following construction. Given digraphs $D_1,D_2$, and a root vertex $v\in D_2$, the  \textit{rooted product digraph}, denoted $D_1\circ_v D_2$, is obtained by gluing a copy of $D_2$ at $v$ to each vertex of $D_1$, see \Cref{fig:rooted product} for an example.
\begin{figure}[h]
    \centering
    \begin{tikzpicture}
        \tikzset{shorten >= 6pt};
        \coordinate (P3base) at (-6,0);
        \coordinate (K3base) at (-2,0);
        \coordinate (prodbase) at (3,0);
        \coordinate (label) at (0,-3);

        \coordinate (p1) at (-2.25,0);
        \coordinate (p2) at (-0.75,0);
        \coordinate (p3) at (0.75,0);
        \coordinate (p4) at (2.25,0);

        \coordinate (k1) at (0,0);
        \coordinate (k2) at (1,-1);
        \coordinate (k3) at (0,-2);

        %p3 edges
         \draw[arrow] ($(P3base) + (p1)$) -- ($(P3base) + (p2)$);
         \draw[arrow] ($(P3base) + (p2)$) -- ($(P3base) + (p3)$);
         \draw[arrow] ($(P3base) + (p3)$) -- ($(P3base) + (p4)$);

    %p3 edges in product
        \draw[arrow] ($(prodbase) + (p1)$) -- ($(prodbase) + (p2)$);
        \draw[arrow] ($(prodbase) + (p2)$) -- ($(prodbase) + (p3)$);
        \draw[arrow] ($(prodbase) + (p3)$) -- ($(prodbase) + (p4)$);

        %product edges and verts
        \foreach \v in {p1,p2,p3,p4}{
            \node[vertexSmall] at ($(P3base) + (\v)$) {};

            \draw[arrow] ($(prodbase) + (\v)$) -- ($(prodbase) + (\v) + (k2)$);
            \draw[arrow] ($(prodbase) + (\v) + (k2)$) -- ($(prodbase) + (\v) + (k3)$);
            \draw[arrow] ($(prodbase) + (\v) + (k3)$) -- ($(prodbase) + (\v)$);
            
            \node[vertexSmall,fill=black] at ($(prodbase) + (\v)$) {};
            \node[vertexSmall] at ($(prodbase) + (\v) + (k2)$) {};
            \node[vertexSmall] at ($(prodbase) + (\v) + (k3)$) {};
        }

        %k3 edges
       \draw[arrow] ($(K3base) + (k1)$) -- ($(K3base) + (k2)$);
       \draw[arrow] ($(K3base) + (k2)$) -- ($(K3base) + (k3)$);
       \draw[arrow] ($(K3base) + (k3)$) -- ($(K3base) + (k1)$);

    %k3 verts
        \node[vertexSmall,fill=black] at ($(K3base) + (k1)$) {};
        \node[vertexSmall] at ($(K3base) + (k2)$) {};
        \node[vertexSmall] at ($(K3base)  + (k3)$) {};

        %labels
        \node[draw] at ($(P3base) + (label)$) {$\ora{P_4}$};
        \node[draw] at ($(K3base) + (label)$) {$\ora{K_3}$};
        \node[draw] at ($(prodbase) + (label)$) {$\ora{P_4}\circ_v \ora{K_3}$};

        %vertex v
        \node[above right=2pt and 2pt of K3base]  {$v$};
        
        
        

        
    \end{tikzpicture}
    \caption{The rooted product digraph $\ora{P_4} \circ_v \ora{K_3}$ with the vertex $v$ highlighted in black.}
    \label{fig:rooted product}
\end{figure}

 This product was first defined by Godsil and McKay \cite{godsil1978new}, and it turns out that this operation plays very nicely with the Eulerian polynomial.
    \begin{prop}\label{prop: rooted product graphs}
        Let $D_1$ and $D_2$ be two digraphs on $m$ and $n$ vertices respectively. If $v\in D_2$, then 
        \[A_{D_1\circ_v D_2}(t)=\frac{1}{m!}\binom{mn}{n,\ldots,n} A_{D_1}(t)A_{D_2}(t)^m.\]
        In particular, the polynomial is the same for any choice of root $v\in D_2$.
    \end{prop}

    \begin{remark}
    The last line of the statement implies that there are non-isomorphic  digraphs with the same Eulerian polynomial.
\end{remark}

With this, we first consider the case when $n=2^m$ for some $m\geq 1$. Let $P_2$ be the graph on vertices $v_1,v_2$ with a single arc $v_1\to v_2$. Define a sequence of digraphs $\{L_m\}_{m\in \N}$ by
     \[
        L_1 = P_2~~~~\text{and}~~~ L_{m + 1} = L_m\circ_{v_1} P_2.
     \] We observe that $L_{m}$ has $2^m$ vertices and $2^m - 1$ arcs. Then from \Cref{prop: rooted product graphs}, we have
     \[ 
        \A_{L_m}(t) = (2^m)!\left(\frac{1 + t}{2}\right)^{2^m - 1}.
     \] Since $s_2(2^m) = 1$, this gives the desired construction when $n$ is a power of two. For arbitrary $n$, we let $a_1,\dots,a_\ell$ be the indices of nonzero powers of $2$ in the binary expansion of $n$ and then define $D$ to be the disjoint union of the digraphs $L_{a_1},\dots, L_{a_\ell}$. Then $A_D(t)$ gives the desired upper bound. 




We also obtain a general lower bound on $\mult(A_D(t),-1)$.
\begin{prop}\label{prop:matching}
    Let $D$ be an orientation of an $n$-vertex graph $G$.  If every matching in the complement of $G$ has size at most $m$, then  $\mult(\A_D(t),-1) \geq \floor{\frac{n}{2}} - m$.
\end{prop}

Roughly speaking, \Cref{prop:matching} says that if $G$ is ``dense'' (i.e.\ if the complement of $G$  contains small only matchings), then $\mult(A_D(t),-1)$ will be large. While \Cref{prop:matching} is not tight in general, it turns out to be tight if $D$ is an orientation of the complete graph as we show now.

 Let $OP(\alpha)$ denote the set of all ordered set partitions of type $\alpha$, and let $SP(\lambda)$ denote the set of all unordered set partitions with type $\lambda$. For two sets $S,T$ of vertices in a digraph $D$, let $e_D(S,T)$ be the number of edges which start in $S$ and end in $T$. For a digraph $D$ and an ordered set partition $P=(P_1,\dots,P_k)$ of the vertices of $D$ of length $k$ and $i \in [k]$, define the \textit{$i$-th forward sequence number} of $P$  to be \[FS_{D,P}(i) = \sum_{j = i + 1}^{k} e_D(P_i,P_j)\] and the \textit{$i$-th reverse sequence number} of $P$ to be \[RS_{D,P}(i) = \sum_{j = i + 1}^{k} e_D(P_j,P_i)\] where we set $FS_{D,P}(k) = 0$ and $RS_{D,P}(1) = 0$. 
 % Note that $FS_{D,P}(i)=e_D(P_i,P_{i+1}\cup \cdots P_k)$ and $RS_{D,P}(i)=e_D(P_{i+1}\cup \cdots P_k,P_i)$. 

  With this notation in hand, we can factor the Eulerian polynomial.
  \begin{lemma}\label{lemma ordered set partition expansion}
    If $D$ is a tournament on the vertex set $[n]$ and $\alpha$ is the integer composition $(2^k)$ of~$n$ if $n$ is even and $(1,2^k)$ if $n$ is odd, then
    \[
        \A_D(t) = (1+t)^k\frac{1}{2^{k}}\sum_{P\in OP(\alpha)} \prod_{i = 1}^{k}  t^{FS_{D,P}(i)} + t^{RS_{D,P}(i)}.
    \]
 \end{lemma}



A parity argument shows that the sum in the lemma does not have -1 as a root. Therefore, we obtain the following.

\begin{theorem}\label{thm: -1 multiplicity for tournaments}
    If $D$ is a tournament on $n$ vertices, then $\mult(A_D(t),-1)=\lfloor\frac{n}{2}\rfloor$.
\end{theorem}
More generally, we suspect that \Cref{prop:matching} is tight for orientations of complete multipartite graphs; see \Cref{conj:multipartite} for more.


Given \Cref{thm: -1 multiplicity for tournaments} and the fact that $|A_D(-1)|=|A_{D'}(-1)|$ whenever $D,D'$ are orientations of the same graph, it is perhaps natural to guess that $\mult(A_D(t),-1)$ depends only on the underlying graph of $D$.  This turns out to be false; see \Cref{fig:-1 multiplicity changes with orientation} for a counterexample.

    \begin{figure}[hbpt]
        \centering
        \begin{tikzpicture}
        

        %coordinates
        \coordinate (a) at (0:2);
        \coordinate (b) at (72:2);
        \coordinate (c) at (144:2);
        \coordinate (d) at (216:2);
        \coordinate (e) at (288:2);

        \coordinate (base1) at (-6,0);
        \coordinate (base2) at (1,0);

        %D1 vertex set
        \node[vertex] (A1) at ($(a) + (base1)$) {$v_1$};
        \node[vertex] (B1) at ($(b) + (base1)$) {$v_2$};
        \node[vertex] (C1) at ($(c) + (base1)$) {$v_3$};
        \node[vertex] (D1) at ($(d) + (base1)$) {$v_4$};
        \node[vertex] (E1) at ($(e) + (base1)$) {$v_5$};

        %D2 vertex set
        \node[vertex] (A2) at ($(a) + (base2)$) {$v_1$};
        \node[vertex] (B2) at ($(b) + (base2)$) {$v_2$};
        \node[vertex] (C2) at ($(c) + (base2)$) {$v_3$};
        \node[vertex] (D2) at ($(d) + (base2)$) {$v_4$};
        \node[vertex] (E2) at ($(e) + (base2)$) {$v_5$};
        
        %D1
        \draw[arrow] (A1) -- (B1);
        \draw[arrow,line width=2pt] (B1)-- (C1);
        \draw[arrow] (C1)-- (D1);
        \draw[arrow](D1) -- (E1);
        \draw[arrow] (A1) -- (C1);
        \draw[arrow] (C1) -- (E1);
        \draw[arrow] (B1) -- (D1);


        %D2
        \draw[arrow] (A2) -- (B2);
        \draw[arrow,line width=2pt] (C2) -- (B2);
        \draw[arrow] (C2) -- (D2);
        \draw[arrow] (D2) -- (E2);
        \draw[arrow] (A2) -- (C2);
        \draw[arrow] (C2) -- (E2);
        \draw[arrow] (B2) -- (D2);
        
        \end{tikzpicture}
        \caption{Two orientations of the same graph with different $-1$ multiplicities. 
 The digraph on the left has $\A_{D_1}(t) = (1 + t)^3 (1 + t + 11 t^2 + t^3 + t^4)$ while the one on the right has $\A_{D_2}(t) = (1 + t) (1 + 5 t + 16 t^2 + 16 t^3 + 16 t^4 + 5 t^5 + t^6)$.}
        \label{fig:-1 multiplicity changes with orientation}
    \end{figure}
\section{Concluding Remarks and Open Problems}\label{sec conclusion}
In this extended abstract, we studied a notion of Eulerian polynomials $\A_D(t)$ for digraphs $D$ and proved a number of results related to evaluations at $t=-1$.  We conclude by listing a number of remaining open problems themed around interpreting $\nu(G)$ and multiplicities of $-1$ as a root of $\A_D(t)$.

\textbf{Interpretations for $\nu(G)$}.  Recall that for any graph $G$ we define $\nu(G)=|\A_D(-1)|$ where $D$ is any orientation of $G$.  While \Cref{thm:nuEta} provides a combinatorial interpretation for $\nu(G)$ when $G$ is bipartite, complete bipartite, or a blowup of a cycle, we are still far from understanding this quantity for general graphs, which we leave as the main open problem for this paper.

\begin{question}\label{quest:combInterp}
    Can one give a combinatorial interpretation for $\nu(G)$ for arbitrary graphs $G$?
\end{question}
In view of \Cref{thm:nuEta} and the bound $\nu(G)\le \eta(G)$ from \Cref{lem:etaRecurrence}(a), we suspect that in general $\nu(G)$ should count even sequences of $G$ with some special properties, but what these properties should be remains a mystery.

To answer \Cref{quest:combInterp}, it might be useful to establish which graphs $G$ satisfy $\nu(G)=\sum_v \nu(G-v)$, as recurrences of this form were a key step in proving \Cref{thm:nuEta}.   In particular, computational evidence suggests that the following could hold, where here we recall that a graph is \textit{Eulerian} if all of its degrees are even.
\begin{conjecture}\label{conj:Eulerian}
    If $G$ is an Eulerian graph, then $\nu(G)=\sum_v \nu(G-v)$.
\end{conjecture}
We note that an Eulerian graph has a ``natural'' orientation via orienting each edge according to an Eulerian tour.  Given that e.g.\ our proof of \Cref{cor:nuBipartite} relied on ``natural'' orientations of bipartite graphs, it is plausible that this natural orientation for Eulerian graphs could be used to prove \Cref{conj:Eulerian}.

Our proof of \Cref{thm:nuEta} is non-combinatorial, and it would be interesting to have a more direct combinatorial proof of this fact, say for bipartite graphs.

\begin{prob}
    For any bipartite graph $G=([n],E)$ and orientation $D$ of $G$, construct an explicit involution $\phi:\mathfrak{S}_n\to \mathfrak{S}_n$ such that
    \begin{enumerate}
        \item[(a)] The set of fixed points $\mathcal{F}_\phi$ of $\phi$ is the set of (inverses of) even sequences of $G$, and
        \item[(b)] $(-1)^{\des_D(\sig)}=-(-1)^{\des_D(\phi(\sig))}$ for all $\sig\notin \mathcal{F}_\phi$.
    \end{enumerate}
\end{prob}

Such an involution is known to exist when $G=P_n$ (i.e.\ when inverses of even sequences are exactly alternating permutations), but this involution is somewhat complex; see \cite[Exercise 135]{stanley_2011} for more.

\textbf{Multiplicity of Roots}.  In \Cref{thm: -1 multiplicity for tournaments} we showed every $n$ vertex tournament $D$ has $-1$ as a root of $\A_D(t)$ with multiplicity exactly $\floor{\frac{n}{2}}$. A natural generalization of this result would be the following. 
\begin{conjecture}\label{conj:multipartite}
    If $D$ is the orientation of a complete multipartite graph which has $r$ parts of odd size, then $\mult(\A_D(t),-1)=\floor{\frac{r}{2}}$.
\end{conjecture}
Observe that the bound $\mult(A_D(t),-1)\ge \floor{\frac{r}{2}}$ follows from \Cref{prop:matching}, so the difficulty lies in proving the upper bound. 


Another direction is to look at the more general quantity $\mult(A_D(t),\alpha)$, which is defined to be the multiplicity of $\alpha$ as a root of $A_D(t)$.  For example, it is not difficult to see that $\mult(A_D(t),0)$ is equal to the minimum number of arcs that one must remove in $D$ to obtain an acyclic digraph.  Such a set of arcs is known as a \textit{minimum feedback arc set}, and determining the size of such a set is well known to be an NP-Complete problem \cite{karp2010reducibility}.

This connection to feedback arc sets, together with the results of this paper, establishes a number of results for $\mult(A_D(t),\alpha)$ when $\alpha\in \{0,-1\}$, and it is natural to ask what can be said about other integral values of $\alpha$.  An immediate obstacle to this is the following.
\begin{question}
    Does there exist a digraph $D$ such that $A_D(t)$ has an integral root which is not equal to either $0$ or $-1$?
\end{question}
We have verified that no such digraph exists on at most 5 vertices. 
We also note that there exist digraphs with real roots of magnitude larger than $2$, so the obstruction to finding these integral roots is not that their magnitudes are too large.  

\acknowledgements{This work began as part of the Graduate Student Combinatorics Conference 2022, which was funded through NSF Grant DMS-1933360, UC San Diego, and the Combinatorics Foundation.}

\printbibliography



\end{document}



% \subsection{Related Works}

% Before presenting our proofs, we first comment on a variety of similar looking polynomials that appear in the literature.  This summary is by no means exhaustive, as there are countless objects adopting the monikers of \textit{Eulerian numbers}, \textit{Eulerian polynomials}, \textit{descents} or \textit{inversions}; most of which have little to no relation to the problems studied here.

% % As previously mentioned, Foata and Zeilberger \cite{FOATA199679} were the first to define the above polynomial $A_D(t)$. They were primarily interested in finding digraphs $D$ for which the statistic $\des_D$ has the same distribution on $\mathfrak{S}_D$ as another statistic $\maj_D$ which is a generalization of the classical ``major index" permutation statistic. Their problem has a positive answer when $D$ is ``bipartitional'', which in our terminology is a join of bidirected complete graphs and digraphs with no edges. In our \Cref{prop basic facts}(d) we consider more general joins of digraphs which recovers some of the results from \cite{FOATA199679}.

% As previously mentioned, Foata and Zeilberger \cite{FOATA199679} were the first to define the above polynomial $A_D(t)$. They were primarily interested in finding digraphs $D$ for which the statistic $\des_D$ has the same distribution on $\mathfrak{S}_D$ as another statistic $\maj_D$ which is a generalization of the classical ``major index" permutation statistic. 


% % When $D$ is acyclic, $\des_D$ is a \textit{weighted-inversion statistic} as in Kadell \cite{KADELL198522} and Degengardt--Milne \cite{DEGENHARDT200049} which is any function $w:\mathfrak{S}_n\to \Z_{\geq 0}$ of the form
% % \[w(\sigma)=\sum_{\substack{1\leq i<j\leq n\\ \sig(i)>\sig(j)}} w_{i,j}\]
% % for some upper triangular matrix $(w_{i,j})$. In fact, it is easy to see that $\des_D$ encapsulates all weighted inversion statistics $w$ for which $w_{i,j}\in \{0,1\}$ for all $i,j$. 

% When $D$ is acyclic, $\des_D$ is a \textit{weighted-inversion statistic} as in Kadell \cite{KADELL198522} and Degengardt--Milne \cite{DEGENHARDT200049}. Archer et al \cite{ARCHER2020112041} define a \textit{Eulerian polynomial for a family $\mathfrak{B}_n$ of digraphs}. The polynomial $\A_D(t)$ can be recovered from $b_n(u)$ by selecting $\mathfrak{B}_n$ to be \textit{all} labelings of a fixed digraph, although this particular choice of family of digraphs is not considered in \cite{ARCHER2020112041}. The polynomial $A_D(t)$ also appears as specializations of the Ellzey \textit{chromatic quasisymmetric function for digraphs} \cite{Ellzey_2017} as well as the Awan and Bernardi \textit{B-polynomial} \cite{awan_bernardi_2020}. 

% Lastly, we note that Kalai \cite{KALAI2002412} explicitly mentioned the determination of $\A_D(-1)$ as an interesting problem in the context of the Condocet paradox in social choice theory, and Even-Zohar \cite{Even-Zohar2017} gave some basic properties of $\nu(G)$ in their study of the random framed knots through permutation statistics.

% There are a variety of papers which implicitly or explicitly consider the polynomial $\A_D(t)$ \cite{ARCHER2020112041,awan_bernardi_2020,FOATA199679} or a another generalization of the descent statistic to directed graphs \cite{poznanović2023descent}. Our polynomial has some close connections to several of these previous works.

% Archer et al \cite{ARCHER2020112041} define a \textit{Eulerian polynomial for a family $\mathfrak{B}_n$ of digraphs} as
%     \[b_n(u)=\sum_{D\in \mathfrak{B}_n}u^{\des(D)}\]
% where $\des(D)$ is defined by \textit{fixing} a labeling $\omega_D:V(D)\to[n]$ of the vertices of $D$  for each $D$ and then counting the number of edges that go from larger label to smaller label.  The polynomial $\A_D(t)$ can be recovered from $b_n(u)$ by selecting $\mathfrak{B}_n$ to be \textit{all} labelings of a fixed digraph, although this particular choice of family of digraphs is not considered in \cite{ARCHER2020112041}.
% Foata and Zeilberger \cite{FOATA199679} asked the question of when the inversion and major index statistics are equidistributed on a digraph, and in the process explicitly define the polynomial $\A_D(t)$. Their work focuses on ``bipartitional graphs'' which in our terminology is a join of bidirected complete graphs and graphs with no edges. In our proposition \ref{prop basic facts} we consider these graphs and more general joins of graphs. 
% The polynomial $A_D(t)$ also appears as specializations of the Ellzey \textit{chromatic quasisymmetric function for digraphs} \cite{Ellzey_2017} as well as the Awan and Bernardi \textit{B-polynomial} \cite{awan_bernardi_2020}.


% Lastly, we note that Kalai \cite{KALAI2002412} explicitly mentioned the determination of $\A_D(-1)$ as an interesting problem in the context of the Condocet paradox in social choice theory, and Even-Zohar\cite{Even-Zohar2017} gave some basic properties of $\nu(G)$ in their study of the random framed knots through permutation statistics.


% , defined as follows. Let $y$ and $z$ be variables, $q$ a positive integer, and $D = (V,E)$ an arbitrary digraph. The \textit{B-polynomial} is then
%  \[
%     B_D(q,y,z) = \sum_{f:V\to \{1,2,\dots,q\}} y^{\asc_D(f)}z^{\des_D(f)}
%  \] where $\asc_D(f) = \#\{uv\in E: f(u) < f(v)\}$ is the number of \textit{ascents} of the coloring $f$ and $\des_D(f) = \#\{uv\in E: f(u) > f(v)$ is the number of \textit{descents}. As shown in Proposition 3.2(k) in Awan and Bernardi's paper \cite{awan_bernardi_2020}, one can recover our polynomial from theirs via the coefficient of $q^n$ in the B-polynomial, i.e.
%  \[
%     n![q^n]B_D(q,1,t) = \sum_{\sigma\in \mathfrak{S}_n} t^{\des_D(t)} = \A_D(t) 
%  \] where $[q^n]p(q)$ denotes the coefficient of $q^n$ in the polynomial $p(q)$. As Awan and Bernardi's work focuses on connections to the Tutte Polynomial, their work does not directly consider the properties of $\A_D(t)$.

% A function $f:V\to \P$ is a \textit{proper coloring} of a digraph $D=(V,E)$ provided $f(u)\neq f(v)$ whenever $\{u,v\}$ is an edge in the underlying graph. Let $\mathbf{x}=(t_1,x_2,\dots)$ be a infinite set of commuting variables. Then Ellzey \cite{Ellzey_2017}, extending previous work \cite{stanley_1995,shareshian_wachs_2016}, defines the \textit{chromatic quasisymmetric function} of $D$ to be 
%  \[X_D(\mathbf{x},t)=\sum_{f}t^{\des_D(f)}\prod_{v\in V}x_{f(v)}\]
%  where the sum is over all proper colorings of $D$. This quasisymmetric function can be seen as containing our polynomial in the coefficient of the monomial $x_1\dots x_n$ i.e
%  \[[x_1\cdots x_n]X_{D}(\mathbf{x},t)=\A_D(t).\]
    

% \subsection{Organization of the Paper}
The rest of this paper is organized as follows. In \Cref{sec not and basic facts}, we lay out the necessary definitions, notation and elementary properties of $A_D(t)$ for the rest of the paper. In \Cref{sec -1 evaluation} we consider evaluations of $\A_D(t)$ at $t = -1$. In particular, we give  basic properties of $\nu(G)$ in \Cref{subsec:basic}, we prove \Cref{thm:nuEta} in \Cref{subsec:interpretation}, and  we prove \Cref{thm:induced} in \Cref{subsec:induced}. In \Cref{sec bounds for nu on tree} we study the bounds for $\nu(T)$ for trees $T$ and prove \Cref{thm:etaTree}. In \Cref{section: multiplicity} we study the multiplicity of $-1$ as a root of $A_D(t)$ and prove \Cref{prop:matching} and Theorems \ref{thm root multiplicity upper bound} and \ref{thm: -1 multiplicity for tournaments}. We conclude the paper in \Cref{sec conclusion} with a few remarks and open problems regarding $A_D(t)$.

\section{Preliminaries}\label{sec not and basic facts}
% \subsection{Notation}\label{sec preliminaries}	


%     Graphs in this paper will always be finite and simple. An \textit{oriented graph} is a digraph $D$ obtained by taking a graph $G$ and giving an orientation to each of its edges. In this case we say $G$ is the \textit{underlying graph} of $D$ and that $D$ is an \textit{orientation} of $G$.
    

%     We will often denote the vertex set of a graph or digraph by $V(G)$ or $V(D)$ respectively, or simply $V$ whenever $G$ or $D$ is understood; and we similarly use the notation $E(G)$ and $E(D)$. For a subset $S\subseteq V(D)$, we write $D[S]$ for the induced subgraph of $D$ on $S$, and we write $D - S$ for the induced subgraph $D[V\setminus S]$.  We write $\overline{S}$ for the complement $V(D)\sm S$.  For two sets $S,T\subseteq V(D)$, we write $e_D(S,T)$ for the number of arcs  $uv$ whose tail $u$ is in $S$ and whose head $v$ is in $T$.


% An \textit{integer composition} $\alpha$ of $n\in \N$ of length $\ell$ is a sequence $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_\ell)$ of positive integers such that $\alpha_1+\cdots+\alpha_\ell=n$, and for such a sequence we write $\alpha\vdash n$. The elements $\alpha_1,\dots,\alpha_\ell$ of $\alpha$ are sometimes called the \textit{parts} of $\alpha$. If $\alpha_1 \geq \alpha_2 \geq \dots \geq \alpha_\ell$, we say that $\alpha$ is an \textit{integer partition}. The \textit{type} of an integer composition $\alpha$, denoted by $\lambda(\alpha)$, is the integer partition given by sorting the parts of $\alpha$ in weakly decreasing order. We will use the notation $(n)^m$ to denote the integer partition $({n,\dots,n})$ that has $m$ copies of $n$.  

% An \textit{ordered set partition} of a set~$S$ is a sequence $P=(B_1,\dots,B_\ell)$ of mutually disjoint subsets $B_i$ of $S$ called \textit{blocks} such that $\bigcup_{i=1}^\ell B_i= S$. The \textit{type} of a set partition $P$ is the type of the integer composition $(|B_1|,\dots,|B_\ell)|$. An unordered set partition is an ordered set partition with the order forgotten. 

% For positive integers $n_1,\dots,n_r$ and $n=n_1+\cdots+n_r$, the \textit{$t$-multinomial coefficient} is defined to be  \[\begin{bmatrix}
%     n\\ n_1,\ldots,n_r
% \end{bmatrix}_t=\frac{[n]_t!}{[n_1]_t!\cdots [n_r]_t!}\] where $[n]_t!=(1+t)(1+t+t^2)\cdots (1+t+t^2+\cdots+t^{n-1})$. 



%Define the \textit{Eulerian polynomial} of a digraph to be 
	%\[\A_D(t)=\sum_{\sigma\in\mathfrak{S}_V}t^{\des_D(\sigma)}.\]
%When $D$ is the path $\ora{P}_n$ with natural orientation $i\to i+1$ for all $i\in [n-1]$, then $\DES_{P_n}(\sigma)$ is the classical descent set of a permutation and $\A_{P_n}(t)$ is exactly the \textit{Eulerian polynomial} $A_n(t)=\sum_{\sigma\in \mathfrak{S}_n}t^{\des(\sigma)}.$ In this paper, we study $\A_D(t)$ for a variety of different digraphs.



\subsection{Basic Properties}\label{sec basic facts}

% In this subsection, we prove a number of basic facts regarding $\A_D(t)$ which will be used throughout the paper. We begin by establishing a list of elementary properties for $\A_D(t)$.  Some of these properties can be found in Even-Zohar \cite{Even-Zohar2017}; we have included their proofs for completeness. For this, we recall that a polynomial $f(t)=\sum_{k} a(k) t^k$ is \textit{palindromic with center $d/2$} if $a(k)=a(d-k)$ for all $k$. 
In this subsection, we prove a number of basic facts regarding $\A_D(t)$ which will be used throughout the paper. We begin by establishing a list of elementary properties for $\A_D(t)$ (cf. \cite{Even-Zohar2017}). For this, we recall that a polynomial $f(t)=\sum_{k} a(k) t^k$ is \textit{palindromic with center $d/2$} if $a(k)=a(d-k)$ for all $k$. 

\begin{prop}\label{prop basic facts}
    Let $D=(V,E)$ be a directed graph with $n$ vertices and $m$ arcs.
     \begin{enumerate}
        \item[(a)] The polynomial $\A_D(t)$ is palindromic with center $m/2$.
        \item[(b)] If $(u,v),(v,u)\in E$, then $\A_D(t)=t\cdot \A_{D-(u,v)-(v,u)}(t)$.
        \item[(c)] If $D=\bigsqcup_{i=1}^r D_i$ is a disjoint union of digraphs of orders $n_1,\ldots,n_r$, then
        \[\A_D(t)=\binom{n}{n_1,\ldots,n_r} \cdot \prod_{i=1}^r A_{D_i}(t).\]
        \item[(d)] If $D$ is formed by taking the disjoint union of digraphs $D_1,\ldots,D_r$ of orders $n_1,\ldots,n_r$ and then adding all arcs of the form $u\to v$ with $u\in V_i,\ v\in V_j$ and with $i<j$, then
        \[\A_D(t)=\begin{bmatrix} n\\ n_1,\ldots,n_r\end{bmatrix}_t \cdot \prod_{i=1}^r A_{D_i}(t).\]
    \end{enumerate}
\end{prop}
    We note that (b) and (c) allows us to reduce our problems to studying digraphs $D$ which are orientations of connected graphs. 



Next, we have a lemma which allows us to express the Eulerian polynomial of a digraph $D$ in terms of Eulerian polynomials of induced subgraphs of $D$. 
 \begin{lemma}\label{lemma split into subgraphs}
     If $D=(V,E)$ is an $n$-vertex digraph and $k\in [n]$, then
     \[
         \A_D(t) = \sum_{S\in \binom{V}{k}} \frac{t^{e_D(S,\overline{S})} + t^{e_D(\overline{S},S)}}{2}\A_{D[S]}(t)\A_{D - S}(t).
     \]
 \end{lemma}
 



Finally, we consider a construction which will be useful for \Cref{thm root multiplicity upper bound} and \Cref{prop:nuGeneral}. Given digraphs $D_1,D_2$ and a root vertex $v\in D_2$, the  \textit{rooted product digraph}, denoted $D_1\circ_v D_2$, is obtained by gluing a copy of $D_2$ at $v$ to each vertex of $D_1$, see \Cref{fig:rooted product} for an example.
\begin{figure}[h]
    \centering
    \begin{tikzpicture}
        \tikzset{shorten >= 6pt};
        \coordinate (P3base) at (-6,0);
        \coordinate (K3base) at (-2,0);
        \coordinate (prodbase) at (3,0);
        \coordinate (label) at (0,-3);

        \coordinate (p1) at (-2.25,0);
        \coordinate (p2) at (-0.75,0);
        \coordinate (p3) at (0.75,0);
        \coordinate (p4) at (2.25,0);

        \coordinate (k1) at (0,0);
        \coordinate (k2) at (1,-1);
        \coordinate (k3) at (0,-2);

        %p3 edges
         \draw[arrow] ($(P3base) + (p1)$) -- ($(P3base) + (p2)$);
         \draw[arrow] ($(P3base) + (p2)$) -- ($(P3base) + (p3)$);
         \draw[arrow] ($(P3base) + (p3)$) -- ($(P3base) + (p4)$);

    %p3 edges in product
        \draw[arrow] ($(prodbase) + (p1)$) -- ($(prodbase) + (p2)$);
        \draw[arrow] ($(prodbase) + (p2)$) -- ($(prodbase) + (p3)$);
        \draw[arrow] ($(prodbase) + (p3)$) -- ($(prodbase) + (p4)$);

        %product edges and verts
        \foreach \v in {p1,p2,p3,p4}{
            \node[vertexSmall] at ($(P3base) + (\v)$) {};

            \draw[arrow] ($(prodbase) + (\v)$) -- ($(prodbase) + (\v) + (k2)$);
            \draw[arrow] ($(prodbase) + (\v) + (k2)$) -- ($(prodbase) + (\v) + (k3)$);
            \draw[arrow] ($(prodbase) + (\v) + (k3)$) -- ($(prodbase) + (\v)$);
            
            \node[vertexSmall,fill=black] at ($(prodbase) + (\v)$) {};
            \node[vertexSmall] at ($(prodbase) + (\v) + (k2)$) {};
            \node[vertexSmall] at ($(prodbase) + (\v) + (k3)$) {};
        }

        %k3 edges
       \draw[arrow] ($(K3base) + (k1)$) -- ($(K3base) + (k2)$);
       \draw[arrow] ($(K3base) + (k2)$) -- ($(K3base) + (k3)$);
       \draw[arrow] ($(K3base) + (k3)$) -- ($(K3base) + (k1)$);

    %k3 verts
        \node[vertexSmall,fill=black] at ($(K3base) + (k1)$) {};
        \node[vertexSmall] at ($(K3base) + (k2)$) {};
        \node[vertexSmall] at ($(K3base)  + (k3)$) {};

        %labels
        \node[draw] at ($(P3base) + (label)$) {$\ora{P_4}$};
        \node[draw] at ($(K3base) + (label)$) {$\ora{K_3}$};
        \node[draw] at ($(prodbase) + (label)$) {$\ora{P_4}\circ_v \ora{K_3}$};

        %vertex v
        \node[above right=2pt and 2pt of K3base]  {$v$};
        
        
        

        
    \end{tikzpicture}
    \caption{The rooted product digraph $\ora{P_4} \circ_v \ora{K_3}$ with the vertex $v$ highlighted in black.}
    \label{fig:rooted product}
\end{figure}

 This product was first defined by Godsil and McKay \cite{godsil1978new}, and it turns out that this operation plays very nicely with the Eulerian polynomial.
    \begin{prop}\label{prop: rooted product graphs}
        Let $D_1$ and $D_2$ be two digraphs on $m$ and $n$ vertices respectively. If $v\in D_2$, then 
        \[A_{D_1\circ_v D_2}(t)=\frac{1}{m!}\binom{mn}{n,\ldots,n}\cdot  A_{D_1}(t)A_{D_2}(t)^m.\]
        In particular, the polynomial is the same for any choice of root $v\in D_2$.
    \end{prop}

\section{Combinatorial Interpretations of $\nu(G)$}\label{sec -1 evaluation}
In this section, we prove our results regarding $\nu(G):=|\A_D(-1)|$ where $D$ is any orientation of the graph $G$.  As noted in the introduction, $\nu(G)$ is intimately related to the quantity $\eta(G)$, which is the number of even sequences of $G$, i.e.\ the number of orderings $\pi$ of $V(G)$ such that the induced subgraphs $G[\pi_1,\ldots,\pi_i]$ have an even number of edges for all $i$.  As a warmup, we formally establish the connection between alternating permutations and even sequences of paths mentioned in the introduction.
\begin{prop}\label{prop:path}
    Let $P_n$ denote the path graph with vertex set $[n]$.  A permutation $\pi$ of $[n]$ is an even sequence of $P_n$ if and only if $\pi^{-1}$ is an alternating permutation.
\end{prop}



\subsection{Basic Properties of $\nu(G)$}\label{subsec:basic}
In this subsection we prove several basic properties of $\nu(G)$, some of which will be needed for the proof of \Cref{thm:nuEta}.   We begin with a basic but important observation.
\begin{lemma}\label{prop odd edges to evaluation at -1}
    If $G$ has an odd number of edges, then $\nu(G)=0$. Otherwise, $\nu(G)\le \sum_v \nu(G-v)$.
\end{lemma}

% The remainder of our proofs for this section rely heavily on the following special case of \Cref{lemma split into subgraphs}.

%  \begin{cor}\label{lemma remove a vertex}
%      If $D$ is an $n$-vertex digraph, then
%      \[
%         \A_{D}(t) = \sum_{v\in V} \frac{t^{\deg_D^+(v)} + t^{\deg_D^-(v)}}{2}\A_{D - v}(t)
%      \]
%  \end{cor}
 

% For ease of notation, we will often write the summation symbol $\sum_{v\in V}$ in \Cref{lemma remove a vertex} simply as $\sum_v$ or even $\sum$.  This result immediately gives the following. 
% \begin{cor}\label{cor:nuInequality}
%     We have $\nu(G)\le \sum_v \nu(G-v)$.
% \end{cor}


An analog of the result above holds for even sequences.
\begin{lemma}\label{lem:etaRecurrence}
    If $G$ has an odd number of edges, then $\eta(G)=0$.  Otherwise, $\eta(G)=\sum_v \eta(G-v)$.
\end{lemma}


Finally, we introduce two graph operations that play nicely with $\nu(G)$.  Given a set of graphs $G_1,\ldots,G_r$ on disjoint vertex sets, the \textit{join} $\bigvee_{i=1}^r G_i$ is the graph obtained by taking the disjoint union of the $G_i$ graphs and then adding all possible edges between each of the $G_i$ graphs.  Given graphs $G_1,G_2$ and a root vertex $v\in G_2$, the \textit{rooted product graph} $G_1\circ_v G_2$ is obtained by gluing a copy of $G_2$ at $v$ to each vertex of $G_1$.  With all this established, we can state the following results involving $\nu(G)$.

\begin{prop}\label{prop:nuGeneral}
    Let $G$ be an $n$-vertex graph.
    \begin{enumerate}
        \item[(a)] We have $\nu(G)\le \eta(G)$.
        \item[(b)] We have $\nu(G)\le \sum_{v} \nu(G-v)$.
        \item[(c)] If $G=\bigsqcup_{i=1}^r G_i$ is a disjoint union of graphs of orders $n_1,\ldots,n_r$, then \[\nu(G)=\binom{n}{n_1,\ldots,n_r} \cdot \prod_{i=1}^r \nu(G_i).\]
        \item[(d)] If $G=\bigvee_{i=1}^r G_i$ is the join of graphs of orders $n_1,\ldots,n_r$, then
        \[\nu(G)=\left|\begin{bmatrix} n\\ n_1,\ldots,n_r\end{bmatrix}_{-1} \right|\cdot \prod_{i=1}^r \nu(G_i).\]
        \item[(e)] If $G=G_1\circ_v G_2$ with $|V(G_i)|=n_i$, then
        \[\nu(G)=\frac{1}{n_1!}{n_1n_2\choose n_2,\ldots,n_2} \nu(G_1)\nu(G_2)^{n_1}.\]
    \end{enumerate}
\end{prop}


\Cref{prop:nuGeneral} has a number of nice consequences.  For example, (c) and (d) imply that to determine $\nu(G)$ for all graphs $G$, it suffices to do this for graphs $G$ such that $G$ and its complement are both connected.  We also have the following immediate consequences.
\begin{cor}\label{cor:nuGeneral}
    Let $G$ be an $n$-vertex graph.
    \begin{enumerate}
        \item[(a)] If $G$ has a component with an odd number of edges, then $\nu(G)=0$.
        \item[(b)] If every vertex of $G$ has odd degree, then $\nu(G)=0$.
        \item[(c)] If $G$ has a vertex $v$ of degree $n-1$,  then $\nu(G)=0$ if $n$ is even, and otherwise $\nu(G)=\nu(G-v)$.
    \end{enumerate}
\end{cor}


\subsection{Proof of \Cref{thm:nuEta}}\label{subsec:interpretation}
In this section, we prove \Cref{thm:nuEta}, which we recall says that if $G$ is a graph that is either bipartite, complete multipartite, or a blowup of a cycle, then $\nu(G)=\eta(G)$. 

The proofs for each of these cases follows the same basic strategy: We first show that for some ``natural'' orientation $D$ of $G$, we can easily predict the sign of $\A_D(-1)$.  From this we deduce $\nu(G)=\sum \nu(G-v)$, and hence that $\nu(G)=\eta(G)$ since the statistics $\nu,\eta$ satisfy the same recurrence relation. Accordingly, we will only discuss the proof for bipartite graphs in this extended abstract, leaving the other classes of graphs for the full paper.

% We begin with the following ``natural'' orientations for bipartite graphs.

\begin{lemma}\label{lem:bipartiteOrientation}
    Let $D$ be a digraph such that one can partition its vertex set into $U\cup V$ such that every arc $u\to v$ of $D$ has $u\in U$ and $v\in V$. Then
    \[\A_D(-1)\ge 0,\]
    and if $D$ has an even number of arcs, then
    \[\A_D(-1)=\sum_{v\in V(D)}\A_{D-v}(-1).\]
\end{lemma}

\begin{cor}\label{cor:nuBipartite}
    If $G$ is a bipartite graph with an odd number of edges, then $\nu(G)=0$, and otherwise $\nu(G)=\sum_v \nu(G-v)$.
\end{cor}


% We next turn to orientations of complete multipartite graphs.  We begin by establishing the following simple criteria for determining if $\nu(G)=0$.


% \begin{lemma}\label{lem:multipartiteOdd}
%     Let $G$ be a complete multipartite graph on $V_1\cup \cdots \cup V_r$. If $|V_i|$ is odd for at least two values of $i$, then $\nu(G)=\eta(G)=0$.
% \end{lemma}

% We next turn to the ``natural'' orientation of complete multipartite graphs.
% \begin{lemma}\label{lem:multipartiteOrientation}
%     Let $D$ be a digraph with vertex set $V_1\cup \cdots \cup V_r$ and arcs $u\to v$ if and only if $u\in V_i,\ v\in V_j$ and $i<j$.  Then \[\A_D(-1)\ge 0,\]
%     and if $|V_i|$ is odd for at most one value of $i$, then
%     \[\A_D(-1)=\sum_v \A_{D-v}(-1).\]
% \end{lemma}

% From these lemmas, the proof of \Cref{cor:nuBipartite} carries over to give the following.
% \begin{cor}\label{cor:nuMultipartite}
%     If $G$ is a complete multipartite graph with at least two parts of odd size, then $\nu(G)=0$, and otherwise $\nu(G)=\sum_v \nu(G-v)$.
% \end{cor}

% Finally, we prove our lemmas for graphs $G$ which are blowups of cycles, which we recall means that one can partition the vertex set of $G$ into sets $V_1,\ldots,V_r$ (which we will call the \textit{parts} of $G$) such that $uv$ is an edge of $G$ if and only if $u\in V_i$ and $v\in V_{i+1}$ for some $i$, where the indices are taken modulo $r$.  Again we begin with a simple criteria for having $\nu(G)=0$.

% \begin{lemma}\label{lem:cycleOdd}
%     Let $G$ be a blowup of a cycle with parts $V_1,\ldots,V_r$. If $|V_i| |V_{i+1}|$ is odd for an odd number of integers $1\le i\le r$, then $\nu(G)=\eta(G)=0$.
% \end{lemma}


% Our analog of Lemmas~\ref{lem:bipartiteOrientation} and \ref{lem:multipartiteOrientation} will be slightly more complex in the setting of blowups of cycles.  For this, we define our ``natural'' directed analog of blowups of cycles as follows: we say a digraph $D$ is a \textit{blowup of a directed $r$-cycle} if it has vertex set $V_1\cup \cdots \cup V_r$ and arcs of the form $u\to v$ if and only if $u\in V_i$ and $v\in V_{i+1}$ for some $i$.  For such a digraph, we define $m(D)$ to be the number of integers $1\le i\le r$ such that $|V_i|$ and $|V_{i+1}|$ are both odd, i.e.\ such that $|V_i||V_{i+1}|$ is odd. 

% \begin{lemma}\label{lem:cycleOrientation}
%     Let $D$ be a blowup of an $r$-cycle.  
%     \begin{enumerate}
%         \item[(a)] If $m(D)$ is odd, then $\A_D(-1)=0$.
%         \item[(b)] If $m(D)$ is even, then 
%         \[(-1)^{m(D)/2} A_D(-1)\ge 0\]
%         and
%         \[(-1)^{m(D)/2}\A_D(-1)=\sum_{v} (-1)^{m(D-v)/2} \A_{D-v}(-1)\]
%     \end{enumerate}
% \end{lemma}
% Note that the first statement implies that when $m(D-v)$ is odd, $\A_{D-v}(-1)=0$. Hence, the sum in the second statement is a well-defined real number. 



% Again these lemmas give the following corollary.
% \begin{cor}
%     If $G$ is a blowup of a cycle such that $|V_i| |V_{i+1}|$ is odd for an even number of integers $i$, then $\nu(G)=0$, and otherwise $\nu(G)=\sum_v \nu(G-v)$.
% \end{cor}
We are now ready to prove our main result for this subsection.
\begin{proof}[Proof of \Cref{thm:nuEta}]
    We aim to show that $\nu(G)=\eta(G)$ whenever $G$ is bipartite, complete multipartite, or a blowup of a cycle.  We first consider the case that $G$ is bipartite.  We prove this result by induction on $|V(G)|$, the base case $\nu(K_1)=\eta(K_1)=1$ being trivial.    By \Cref{cor:nuBipartite} and \Cref{lem:etaRecurrence}, if $G$ has an odd number of edges then $\nu(G)=\eta(G)=0$, and otherwise
    \[\nu(G)=\sum_v \nu(G-v)=\sum_v \eta(G-v)=\eta(G),\]
    where the middle equality used the inductive hypothesis (and that $G-v$ is bipartite whenever $G$ is).  
\end{proof}

It is tempting to try to generalize the approach of this subsection by finding ``natural'' orientations of other graphs in order to show $\nu(G)=\sum \nu(G-v)$; see for example \Cref{conj:Eulerian}.  However, we emphasize that \Cref{thm:induced} shows that the inductive proof of \Cref{thm:nuEta} can not be extended beyond the class of graphs which are bipartite, complete multipartite, or blowups of cycles.


% Before moving on, we note the following cute consequence of our results for $\nu(G)$ which gives a combinatorial interpretation for $t$-multinomial coefficients evaluated at $-1$.
% \begin{cor}\label{cor:multinomial}
%     If $n_1,\ldots,n_r$ are positive integers and $n=n_1+\cdots+n_r$, then
%     \[
%     \left|\begin{bmatrix}
%    n\\ n_1,\ldots,n_r
% \end{bmatrix}_{-1}\right|=\begin{cases}
% 0&\text{at least two parts of odd size}\\
%     \binom{\lfloor n/2\rfloor}{\lfloor n_1/2\rfloor,\dots,\lfloor n_r/2\rfloor}&\text{otherwise.}
% \end{cases}
% \]

% \end{cor}
% It is likely that \Cref{cor:multinomial} is already well known in the literature, though the only concrete source we are aware of is \cite[Section 5.2]{ajose_2007} which solves the case $r=2$ (from which the general result can be derived).


\subsection{Proof of \Cref{thm:induced}}\label{subsec:induced}
In this subsection we characterize which graphs have $\nu(G')=\eta(G')$ for all induced subgraphs $G'\sub G$.  For this the following will be crucial.
\begin{definition}\label{def:pans}
    We define the \textit{odd pan graph} $C_{2k+1}^*$ to be the graph obtained by taking the odd cycle $C_{2k+1}$ and then adding a new vertex $u$ adjacent to exactly one vertex of $C_{2k+1}$; see \Cref{fig: c7star}.  We say that a graph $G$ is \textit{odd pan-free} if it contains no induced subgraph which is isomorphic to $C_{2k+1}^*$ for any $k\ge 1$.
\end{definition}
We note that some authors use the term ``odd pan'' only to refer to $C_{2k+1}^*$ when $k\ge 2$, but we emphasize that we include the paw graph $C_3^*$ in our definition of odd pans. Our motivation for this definition is the following lemma.

\begin{lemma}\label{lem:pans}
    We have $\nu(C_{2k+1}^*)\ne \eta(C_{2k+1}^*)$ for all $k\ge 1$.
\end{lemma}



\begin{figure}[h]
    \centering
    \begin{subfigure}[b]{.4\textwidth}
    \begin{tikzpicture}
    \tikzstyle{vertex} = [circle,draw=black, minimum size=2pt];

        %coordinates
        \coordinate (4) at (-90:2);
        \coordinate (4sub) at (-90:4);
        \coordinate (5) at ({-90+1*51.42}:2);
        \coordinate (6) at ({-90+2*51.42}:2);
        \coordinate (7) at ({-90+3*51.42}:2);
        \coordinate (1) at ({-90+4*51.42}:2);
        \coordinate (2) at ({-90+5*51.42}:2);
        \coordinate (3) at ({-90+6*51.42}:2);


        %D1 vertex set
        \node[vertex] (v4) at (4) {$v_4$};
        \node[vertex] (u) at (4sub) {$u$};
        \node[vertex] (v5) at (5) {$v_5$};
        \node[vertex] (v6) at (6) {$v_6$};
        \node[vertex] (v7) at (7) {$v_7$};
        \node[vertex] (v1) at (1) {$v_1$};
        \node[vertex] (v2) at (2) {$v_2$};
        \node[vertex] (v3) at (3) {$v_3$};

        %D1
         \draw (u) -- (v4)--(v5)--(v6)--(v7)--(v1)--(v2)--(v3)--(v4);
         \node (sp) at (0,0) {~};
         \node (sp) at (3,0) {~};
         \node (sp) at (-3,0) {~};
        \end{tikzpicture}
        \caption{$C_7^*$}
        \label{fig: c7star}
    \end{subfigure}
    \begin{subfigure}[b]{.4\textwidth}
    
        \begin{tikzpicture}
\tikzstyle{vertex} = [circle,draw=black, minimum size=1pt];
        %coordinates
        \coordinate (4) at (-90:2);
        \coordinate (4sub) at (-90:4);
        \coordinate (5) at ({-90+1*51.42}:2);
        \coordinate (6) at ({-90+2*51.42}:2);
        \coordinate (7) at ({-90+3*51.42}:2);
        \coordinate (1) at ({-90+4*51.42}:2);
        \coordinate (2) at ({-90+5*51.42}:2);
        \coordinate (3) at ({-90+6*51.42}:2);


        %D1 vertex set
        \node[vertex] (v4) at (4) {$5$};
        \node[vertex] (u) at (4sub) {$1$};
        \node[vertex] (v5) at (5) {$2$};
        \node[vertex] (v6) at (6) {$6$};
        \node[vertex] (v7) at (7) {$3$};
        \node[vertex] (v1) at (1) {$7$};
        \node[vertex] (v2) at (2) {$4$};
        \node[vertex] (v3) at (3) {$8$};

        %D1
         \draw (u) -- (v4)--(v5)--(v6)--(v7)--(v1)--(v2)--(v3)--(v4);
         \node (sp) at (0,0) {~};
         \node (sp) at (3,0) {~};
         \node (sp) at (-3,0) {~};
        \end{tikzpicture}
        \caption{An even sequence}
        \label{fig: c7star even sequence}
    \end{subfigure}
    \caption{}
    \label{fig:c7star and c7star even sequence}
\end{figure}


% \begin{figure}[h]
%     \centering
%     \begin{subfigure}[b]{.4\textwidth}
%         \begin{tikzpicture}
%         \tikzstyle{vertex} = [circle,draw=black, minimum size=2pt];
%         \tikzstyle{arrow} = [line width=1pt,->];

%         %coordinates
%         \coordinate (4) at (-90:2);
%         \coordinate (4sub) at (-90:4);
%         \coordinate (5) at ({-90+1*51.42}:2);
%         \coordinate (6) at ({-90+2*51.42}:2);
%         \coordinate (7) at ({-90+3*51.42}:2);
%         \coordinate (1) at ({-90+4*51.42}:2);
%         \coordinate (2) at ({-90+5*51.42}:2);
%         \coordinate (3) at ({-90+6*51.42}:2);


%         %D1 vertex set
%         \node[vertex] (v4) at (4) {$2$};
%         \node[vertex] (u) at (4sub) {$5$};
%         \node[vertex] (v5) at (5) {$1$};
%         \node[vertex] (v6) at (6) {$7$};
%         \node[vertex] (v7) at (7) {$3$};
%         \node[vertex] (v1) at (1) {$6$};
%         \node[vertex] (v2) at (2) {$4$};
%         \node[vertex] (v3) at (3) {$8$};

%         %D1
%          \draw[arrow] (u) -- (v4);
%          \draw[arrow](v4)--(v5);
%          \draw[arrow](v5)--(v6);
%          \draw[arrow](v6)--(v7);
%          \draw[arrow](v4)--(v3);
%          \draw[arrow](v3)--(v2);
%          \draw[arrow](v2)--(v1);
%          \draw[arrow](v1)--(v7);
%          \node (sp) at (0,0) {~};
%          \node (sp) at (3,0) {~};
%          \node (sp) at (-3,0) {~};
%          \draw[<->,shorten >=.25cm ,shorten <=.25cm](v3)--(v5);
%          \draw[<->,shorten >=.25cm ,shorten <=.25cm](v2)--(v6);
%          \draw[<->,shorten >=.5cm ,shorten <=.5cm]($(v1)+(0,.5)$)--($(v7)+(0,.5)$);
%         \end{tikzpicture}
%         \caption{$\sigma$}
%         \label{fig: c7star iota1}
%     \end{subfigure}
%     \begin{subfigure}[b]{.4\textwidth} 
%         \begin{tikzpicture}
% \tikzstyle{vertex} = [circle,draw=black, minimum size=2pt];
%         %coordinates
%         \coordinate (4) at (-90:2);
%         \coordinate (4sub) at (-90:4);
%         \coordinate (5) at ({-90+1*51.42}:2);
%         \coordinate (6) at ({-90+2*51.42}:2);
%         \coordinate (7) at ({-90+3*51.42}:2);
%         \coordinate (1) at ({-90+4*51.42}:2);
%         \coordinate (2) at ({-90+5*51.42}:2);
%         \coordinate (3) at ({-90+6*51.42}:2);


%         %D1 vertex set
%         \node[vertex] (v4) at (4) {$2$};
%         \node[vertex] (u) at (4sub) {$5$};
%         \node[vertex] (v5) at (5) {$8$};
%         \node[vertex] (v6) at (6) {$4$};
%         \node[vertex] (v7) at (7) {$6$};
%         \node[vertex] (v1) at (1) {$3$};
%         \node[vertex] (v2) at (2) {$7$};
%         \node[vertex] (v3) at (3) {$1$};

%         %D1
%          \draw[arrow] (u) -- (v4);
%          \draw[arrow](v4)--(v5);
%          \draw[arrow](v5)--(v6);
%          \draw[arrow](v6)--(v7);
%          \draw[arrow](v4)--(v3);
%          \draw[arrow](v3)--(v2);
%          \draw[arrow](v2)--(v1);
%          \draw[arrow](v1)--(v7);
%         %extra arrows
%          \draw[<->,shorten >=.25cm ,shorten <=.25cm](v3)--(v5);
%          \draw[<->,shorten >=.25cm ,shorten <=.25cm](v2)--(v6);
%          \draw[<->,shorten >=.5cm ,shorten <=.5cm]($(v1)+(0,.5)$)--($(v7)+(0,.5)$);
%          \node (sp) at (0,0) {~};
%          \node (sp) at (3,0) {~};
%          \node (sp) at (-3,0) {~};
%     \end{tikzpicture}
%         \caption{$\tau=\iota(\sigma)$}
%         \label{fig: c7star iota2}
%     \end{subfigure}
%     \caption{The involution $\iota$}
%     \label{fig:c7star involution}
% \end{figure}
    

Recall that \Cref{thm:induced} says that if $G$ is a connected graph, then $\nu(G')=\eta(G')$ for all induced subgraphs $G'\sub G$ if and only if $G$ is bipartite, complete multipartite, or a blowup of a cycle.  In view of the lemma above, it will suffice to prove the following structural graph theory lemma.
\begin{prop}\label{prop:structure}
    If $G$ is a connected graph, then $G$ is odd pan-free if and only if it is either bipartite, complete multipartite, or a blowup of a cycle.
\end{prop}
% We will prove this proposition through the following two lemmas.


% \begin{lemma}\label{lem:multipartitePan}
%     If $G$ be a connected graph which is odd pan-free and which contains a triangle, then $G$ is a complete multipartite graph.
% \end{lemma}




% The next lemma deals with the case when $G$ is triangle-free.  Here we recall that a graph is a blowup of a cycle if it has vertex set $V_1\cup \cdots \cup V_r$ and edges $uv$ if and only if $u\in V_i$ and $v\in V_{i+1}$ for some $i$. 
% \begin{lemma}\label{lem:cyclePan}
%     If $G$ be a connected graph which is odd pan-free and which is triangle-free but not bipartite, then $G$ is a blowup of a cycle.
% \end{lemma}


% With these two lemmas we can easily prove \Cref{prop:structure}, and again we recall that this immediately implies \Cref{thm:induced} when combined with \Cref{lem:pans}.



\section{Optimal bounds on \texorpdfstring{$\nu(T)$}{} for trees}\label{sec bounds for nu on tree}
Here we prove \Cref{thm:etaTree}, which we recall says that if $T$ is a tree on $2n+1$ vertices, then
    \[n! 2^n\le \nu(T)=\eta(T)\le (2n)!,\]
    with equality holding in the lower bound if and only if $T$ is a hairbrush, and equality holding in the upper bound if and only if $T$ is a star.

To aid with our proofs, given a tree $T$, we define 
\[\X(T)=\{x\in V(T):\textrm{each component of }T-x\textrm{ has an even number of edges}\},\]
and we will denote this simply by $\X$ whenever $T$ is understood.  Our motivation for this definition is the following.
\begin{lemma}%\label{cor:treeInductiveHypothesis}
    If $T$ is a tree with an even number of edges, then
    \[\nu(T)=\sum_{x\in \X} \nu(T-x).\]
\end{lemma}

With this lemma in mind, the idea for the proofs of the upper and lower bounds is as follows: we first apply \Cref{cor:treeInductiveHypothesis} and then  use induction to bound each of the terms $\nu(T-x)$ in the sum. Finally, we bound our total sum in terms of  $|\X|$ and show that equality can only occur when $|\X|=1$.

% Throughout our proofs, we make heavy use of the fact that if $T'$ is a graph on $2n$ vertices with connected components $T_1,\ldots,T_r$ and $n_i=|V(T_i)|$, then
% \begin{equation}\nu(T')={2n\choose n_1,\ldots,n_r} \prod_{i=1}^r \nu(T_i),\label{eq:treeDisjoint}\end{equation}
% which follows from \Cref{prop:nuGeneral}(c).






\subsection{Lower bound for $\nu(T)$}
Here we prove that $\nu(T)\geq n!2^n$ for all trees $T$ with $2n+1$ vertices with equality when $T$ is the \textit{hairbrush $H_n$}. Recall that this graph $H_n$ is obtained by starting with a path $v_0-v_1-\cdots-v_n$ and then adding a leaf $u_i$ to each $v_i$ for $i\in [n]$; see \Cref{fig: the hairbrush c3}.  We begin by observing the following. It is not too dificult to show that $\nu(H_n)=n!2^n$.

\begin{figure}[h]
    \centering
    \begin{tikzpicture}
    \node[vertex] (v0) at (0,0) {$v_0$};
    \node[vertex] (v1) at (1,0) {$v_1$};
    \node[vertex] (v2) at (2,0) {$v_2$};
    \node[vertex] (v3) at (3,0) {$v_3$};
    \node[vertex] (u1) at (1,-1) {$u_1$};
    \node[vertex] (u2) at (2,-1) {$u_2$};
    \node[vertex] (u3) at (3,-1) {$u_3$};
    \draw[edge] (v0)--(v1)--(v2)--(v3);
    \draw[edge] (v1)--(u1);
    \draw[edge] (v2)--(u2);
    \draw[edge] (v3)--(u3);
    \end{tikzpicture}
    \caption{The hairbrush $H_3$}
    \label{fig: the hairbrush c3}
\end{figure}


% \begin{lemma}\label{lem:hairbrushEta}
%     For $n\geq 0$, the hairbrush $H_n$ has $\nu(H_n)=n!2^n$. 
% \end{lemma}

In view of \Cref{cor:treeInductiveHypothesis}, to show that $\nu(T)>0$ (let alone that $\nu(T)\ge n! 2^n$), it is necessary to show the following.

\begin{lemma}\label{lem:treeNonzero}
    If $T$ is a tree with an even number of edges, then $\X\ne \emptyset$.
\end{lemma}


We will also need the following simple arithmetic inequality. 

\begin{lemma}\label{lem:treeArithmetic}
    Let $n$ be a non-negative integer and $(k_1,\ldots,k_r)$ a sequence of non-negative integers such that $r$ is even, and such that $n=r/2+\sum k_i$.  Then
    \[\prod_{i=1}^r \frac{k_i!}{2(2k_i+1)!}\ge \frac{(n-1)!}{2(2n-1)!},\]
    with equality if and only if $r=2$ and $\{k_1,k_2\}=\{n-1,0\}$.
\end{lemma}

We now prove our lower bound for trees, which we restate below.
\begin{prop}\label{prop:lowerTree}
    If $T$ is a tree on $2n+1$ vertices, then $\nu(T)\geq 2^nn!$ with equality if and only if $T$ is the hairbrush $H_n$.
\end{prop}

\begin{proof}
    We prove the result by induction on $n$, the $n=0$ case being trivial.  Assume we have proven the result up to some value $n$ and let $T$ be a tree on $2n+1$ vertices.

    By \Cref{cor:treeInductiveHypothesis} and the claim above, we have
    \begin{equation}\nu(T)=\sum_{x\in \X} \nu(T-x)\ge |\X|\cdot n! 2^n\ge n! 2^n,\label{eq:oneX}\end{equation}
    with this last inequality using \Cref{lem:treeNonzero}.  This gives the desired lower bound on $\nu(T)$. 

    Now suppose $\nu(T)=n! 2^n$.  This implies both inequalities of \eqref{eq:oneX} are equalities, which can only hold if $|\X|=1$, say with $\X=\{x\}$; and if $T-x$ consists of an isolated vertex $y$ together with a hairbrush $H_{n-1}$.  It remains to show that this implies $T$ must be the hairbrush $H_n$, for which it suffices to show that $x$ is adjacent to $v_{n-1}$ in $H_{n-1}$.
    
     If $x$ is adjacent to some $v_i$ or $u_i$ with $i\in [n-2]$, then $T-v_{n-1}$ has 2 components each with an even number of edges ($2n$ and 0 respectively), so $v_{n-1}\in \X$, a contradiction to $\X=\{x\}$. If $x$ is adjacent to $u_{n}$, then $T-v_{n-1}$ has 2 components each with an even number of edges ($2n-2$ and 2 respectively), so $v_{n-1}\in \tilde{X}$. Thus, in all cases, unless $x$ is adjacent to $v_{n-1}$, we have $\X\ne \{x\}$, which is a contradiction. Hence, we conclude that $T$ is $H_{n}$.  
\end{proof}


\subsection{Upper bound for \texorpdfstring{$\nu(T)$}{}}
We will prove that $\nu(T)\leq (2n)!$ for all trees $T$ with $2n+1$ vertices with equality only when $T$ is the \textit{star graph} $K_{1,2n}$, which consists of a center vertex $v_0$ adjacent to $2n$ leaves $v_1,\ldots,v_{2n}$.%; see Figure \ref{fig:star}.

% \begin{figure}[h]
%     \centering
%     \begin{tikzpicture}
%     \tikzstyle{vertex} = [circle,draw=black, inner sep=4pt];
%     \node[vertex] (s) at (-.5,0) {$s$};
%     \node[vertex] (v1) at (-2,-1) {$v_1$};
%     \node[vertex] (v2) at (-.9,-1) {$v_2$};
%     \node (dots) at (0,-1) {$\dots$};
%     %\node[vertex] (vn1) at (1,-1) {$v_{2n-1}$};
%     \node[vertex] (vn) at (1,-1) {$v_{2n}$};
%     \draw[edge] (s)--(v1);
%     \draw[edge] (s)--(v2);
%     %\draw[edge] (s)--(vn1);
%     \draw[edge] (s)--(vn);
%     \end{tikzpicture}
%     \caption{The star $K_{1,2n}$}
%     \label{fig:star}
% \end{figure}
% \SS{I feel like vertex $v_{2n-1}$ might have two large a circle lol.  Personally I think it's fine to just delete this vertex (and also personally I think the situation is clear enough without the figure at all).}

\begin{lemma}
    For all $n\ge 0$, $\nu(K_{1,2n})=(2n)!$.
\end{lemma}




We next prove some structural results regarding the set $\X$.
 

\begin{lemma}\label{lem:ComponentsIntersectingXOfX}
Let $T$ be a tree with an even number of edges.
\begin{enumerate}
    \item[(a)] No vertex $x\in \X$ is a leaf, and no two vertices of $\X$ are adjacent.
    \item[(b)] For $x\in \X$, let $T_1,\dots,T_r$, be the connected components of $T-x$ with $n_i=|V(T_i)|$. If $T_i$ contains $\ell_i$ vertices of $\X$, then $n_i\ge 2\ell_i+1$ for each $i\in [r]$.
\end{enumerate}
\end{lemma}


We are now in position to prove our desired bound on $\nu(T)$.
    \begin{prop}
        If $T$ is a tree on $2n+1$ vertices, then $\nu(T)\leq (2n)!$ with equality if and only if $T$ is the star $K_{1,2n}.$
    \end{prop}



In total, this proposition together with \Cref{prop:lowerTree} completes the proof of \Cref{thm:etaTree}. 


\begin{remark}Our proofs yield slightly stronger bounds on $\nu(T)$ whenever $\X$ is large.   For example, \eqref{eq:oneX} gives the lower bound $\nu(T)\ge |\X| n! 2^n$.  Bounds of this form are known as  \textit{stability results} in extremal graph theory, which roughly are results saying that bounds for a graph $T$ can be substantially improved if $T$ is ``far'' from a unique extremal construction (in our case, $T$ being ``far'' from $H_n,K_{1,2n}$ is measured by having $|\X|$ large). 
\end{remark}


\section{Multiplicity of $-1$}\label{section: multiplicity}
 In this section, we prove Proposition \ref{prop:matching} and Theorems \ref{thm: -1 multiplicity for tournaments} and \ref{thm root multiplicity upper bound} regarding the multiplicity of $-1$ as a root of $\A_{D}(t)$.  We first prove Theorem \ref{thm root multiplicity upper bound} which we restate for convenience.
\begin{theorem}
    If $D$ is an $n$-vertex digraph, then \[\mult(A_D(t),-1)\le n-s_2(n),\] where $s_2(n)$ denotes the number of 1's in the binary expansion of $n$.  Moreover, for all $n$, there exist $n$-vertex digraphs $D$ with $A_D(t)=\frac{n!}{2^{n-s_2(n)}}(1+t)^{n-s_2(n)}$.
\end{theorem}


We next establish our general lower bound, which we restate for convenience.
 \begin{prop}
     Let $D$ be an orientation of an $n$-vertex graph $G$.  If every matching in the complement of $G$ has size at most $m$, then  $\mult(\A_D(t),-1) \geq \floor{\frac{n}{2}} - m$.
 \end{prop}

In particular this result implies $\mult(A_D(t),-1)\ge \floor{\frac{n}{2}}$ for tournaments $D$, but proving this holds with equality requires a refinement of \Cref{lemma split into subgraphs} which requires some additional notation. 


  Let $OP(\alpha)$ denote the set of all ordered set patitions of type $\alpha$, and let $SP(\lambda)$ denote the set of all unordered set partitions with type $\lambda$.  For a digraph $D$ and an ordered set partition $P$ of the vertices of $D$ of length $k$ and $i \in [k]$, define the \textit{$i$-th forward sequence number} of $P$  to be \[FS_{D,P}(i) = \sum_{j = i + 1}^{k} e_D(P_i,P_j)\] and the \textit{$i$-th reverse sequence number} of $P$ to be \[RS_{D,P}(i) = \sum_{j = i + 1}^{k} e_D(P_j,P_i)\] where we set $FS_{D,P}(k) = 0$ and $RS_{D,P}(1) = 0$. Note that $FS_{D,P}(i)=e_D(P_i,P_{i+1}\cup \cdots P_k)$ and $RS_{D,P}(i)=e_D(P_{i+1}\cup \cdots P_k,P_i)$. 

  With this notation in hand, we have the following corollary of Lemma \ref{lemma split into subgraphs}.
  \begin{lemma}\label{lemma ordered set partition expansion}
    If $D$ is a digraph on the vertex set $[n]$ and $n=2k$, we have
    \[
        \A_D(t) = \left(1 + t\right)^k\frac{1}{2^{k}}\sum_{P\in OP((2)^k)} t^{FS_{T,P}(i)} + t^{RS_{T,P}(i)}.
    \] 
 \end{lemma}
 


With the lemma, we can now prove Theorem \ref{thm: -1 multiplicity for tournaments}. We restate the theorem for convenience.
\begin{theorem}\label{theorem -1 multiplcity for even tournaments}
     If $D$ is a tournament on $n$ vertices, then $\mult(\A_D(t),-1) = \lfloor \frac{n}{2}\rfloor$.
\end{theorem}
    \begin{proof}
    We only consider the case when $n = 2k$ for some $k\in \N$, with the odd case being similar.  Let \[p(t) = \frac{1}{2^{k}}\sum_{P\in OP((2)^k)}t^{FS_{T,P}(i)} + t^{RS_{T,P}(i)}.\] We claim that $p(-1) \neq 0$, from which the bound $\mult(A_D(t),-1)\le n/2$ will follow from the inequality above.
    
    We first observe that $FS_{T,P}(i)+ RS_{T,P}(i)$ is always even, as both vertices in $P_i$ are adjacent to every vertex in $P_{i + 1}\cup \dots \cup P_{k}$. Thus for every $P\in OP((2)^k)$ and every $i\in [k]$, \[(-1)^{FS_{T,P}(i)}+ (-1)^{ RS_{T,P}(i)}  = 2(-1)^{FS_{T,P}(i)}.\]  It follows that 
    \[
        p(-1) = \frac{1}{2^{k}}\sum_{P\in OP((2)^k)} \prod_{i = 1}^{k}(2(-1)^{FS_{T,P}(i)}) = \sum_{P\in OP((2)^k)} (-1)^{FS_{T,P}} = \sum_{P\in SP((2)^k)} \sum_{\sigma\in \mathfrak{S}_k} (-1)^{FS_{T,\sigma P}}.
    \] where $\sigma P$ denotes the ordered set partition $(P_{\sigma(1)},\dots,P_{\sigma(k)})$. Then we prove that for all $\sigma\in \mathfrak{S}_k$,
        For all $\sigma\in \mathfrak{S}_k$,
        \begin{equation}
    FS_{T,\sigma P}\equiv_2 FS_{T,P}~~\text{and}~~ RS_{T,\sigma P}\equiv_2 RS_{T,P}.\end{equation} 
    With this and the fact that $|OP(2^k)|=k!|SP(2^k)|$, we can conclude that 
    \[
        p(-1)= k!\sum_{P\in SP(2^k)}(-1)^{FS_{T,P}}.
    \]
    Each $P\in SP((2)^k)$ is a perfect matching on $[2k]$, and there are $(2k - 1)!!$ such perfect matchings. Since $(2k - 1)!!$ is odd, it follows that $p(-1) \neq 0$ as desired. 
\end{proof}





%     \bibliographystyle{amsalpha}
% \bibliography{refs}



%\acknowledgements{\lipsum[20]}

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