%% 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]{FPSAC2025}
\articlenumber{32}
%% 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{paralist, amsmath, amsthm, amssymb, color, graphicx, hyperref, tikz, amssymb}

\usepackage{nicefrac}
\usepackage{dsfont}
\usepackage{mathrsfs}
\usepackage{biblatex}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
%\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{problem}[theorem]{Problem}

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

\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\de}{\delta}
\newcommand{\eps}{\varepsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Om}{\Omega}

\newcommand{\mA}{\mathcal{A}}
\newcommand{\mB}{\mathcal{B}}
\newcommand{\mC}{\mathcal{C}}
\newcommand{\mD}{\mathcal{D}}
\newcommand{\mF}{\mathcal{F}}
\newcommand{\mK}{\mathcal{K}}
\newcommand{\mP}{\mathcal{P}}
\newcommand{\mQ}{\mathcal{Q}}
\newcommand{\mS}{\mathcal{S}}
\newcommand{\mT}{\mathcal{T}}
\newcommand{\mX}{\mathcal{X}}
\newcommand{\mY}{\mathcal{Y}}
\newcommand{\mZ}{\mathcal{Z}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Sn}{\mathfrak{S}}
\newcommand{\pd}{\textup{pd}}
\newcommand{\sF}{\mathscr{F}}
\newcommand{\sS}{\mathscr{S}}
\newcommand{\s}{\text{span}}
\newcommand{\proj}{\text{proj}}

\newcommand{\sse}{\subseteq}
\newcommand{\sli}{\sum\limits}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}

\newcommand{\emp}{\emptyset}

\usepackage{lipsum}

%% define your title in the usual way
\title[Chromatic polynomial via hyperplane arrangements]{Interpreting the chromatic polynomial coefficients via hyperplane arrangements}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[Neha Goregaokar]{\texorpdfstring{Neha Goregaokar\thanks{\href{mailto:ngoregaokar@brandeis.edu}{ngoregaokar@brandeis.edu}}\addressmark{1}}{Neha Goregaokar}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brandeis University, USA}

%% 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{A recent result of Lofano and Paolini expresses the characteristic polynomial of a real hyperplane arrangement in terms of a projection statistic on the regions of the arrangement. We use this result to give an alternative proof for Greene and Zaslavsky's interpretation for the coefficients of the chromatic polynomial of a graph. We also show that this projection statistic has a nice combinatorial interpretation in the case of the braid arrangement, which generalizes to graphical arrangements of natural unit interval graphs. We use this generalization to give a new proof of the formula for the chromatic polynomial of a natural unit interval graph.}

%% 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{math, maths, mathematics}

%% 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, giveninits]{biblatex}
\addbibresource{reference.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}
In \cite{GZ}, Greene and Zaslavsky gave an interpretation for the coefficients of the chromatic polynomial of a graph $G$ in terms of source components of acyclic orientations of $G$ (formally defined in \Cref{bgsec}). Recently, in \cite{LP}, Lofano and Paolini gave an expression for the characteristic polynomial of a hyperplane arrangement $\mA$ as a generating function of the regions of $\mA$, counted according to a projection statistic with respect to a fixed point $v \in \R^n$. %(the dimension of the face of the region that the projection from a point lies in the interior of). 
The goal of this paper is to see how these two results are related in the case of graphical arrangements. 
\begin{definition}\label{grapharr}
    Let $G = ([n], E)$ be a graph. The \emph{graphical arrangement} $\mA_G$ is defined as the collection of the following hyperplanes:
    $$\mA_G := \{H_{i,j} \mid \{i,j\} \in E, i<j\},$$ 
    where $H_{i,j} = \{(x_1, \ldots, x_n) \in \R^n \mid x_i - x_j = 0\}$.
\end{definition}
It is known that for any graph $G$, 
\begin{equation}\label{CC}
    \chi_{G}(t) = \chi_{\mA_G}(t),
\end{equation}
that is, the chromatic polynomial of a graph is equal to the characteristic polynomial of the corresponding graphical arrangement.
%\begin{theorem}\label{CC}
%    For any graph $G$, we have $$\chi_{G}(t) = \chi_{\mA_G}(t),$$ that is, the chromatic polynomial of a graph is equal to the characteristic polynomial of the corresponding graphical arrangement. 
%\end{theorem}
Further, we can label each region of the graphical arrangement with a unique acyclic orientation of $G$. 

This raises the question of whether there exists a point $v \in \R^n$ such that for each region of $\mA_G$, the projection statistic given in \cite{LP} equals the number of source components of the acyclic orientation of $G$ labeling the region as given in \cite{GZ}. In \Cref{gasec}, we find a set of points in $\R^n$ such that this holds (see \Cref{graphSC}). This shows that the Greene and Zaslavsky result can be obtained using the Lofano and Paolini statistic. 

%In \Cref{gasec}, we find a set of points such that for each region of the graphical arrangement, the projection statistic equals the number of source components of the acyclic orientation corresponding to that region (see \Cref{graphSC}).

We get a particularly nice combinatorial interpretation of this projection statistic in the case of the braid arrangement $\mB_n = \mA_{K_n}$ (see \Cref{braidRLmin}), which generalizes to natural unit interval graphs (see \Cref{NUIProjRL}). We use this interpretation to give an alternative proof of the form of the chromatic polynomial of a natural unit interval graph (see \Cref{NUIChar}). 

\begin{remark}
   Zaslavsky's theorem states that the number of regions of a hyperplane arrangement $\mA$ is $(-1)^n\chi_{\mA}(-1)$. Hence, we can expect to find an expression for $\chi_{\mA}$ as a statistic on the regions of $\mA$. No such statistic was known until the recent results of Lofano and Paolini~\cite{LP} and Kabluchko~\cite{Kabluchko}. Our work shows that this projection statistic can be viewed as a natural combinatorial statistic in the case of graphical arrangements. %Our work uses these results to produce natural combinatorial statistics in the case of graphical arrangements. 
\end{remark}

\section{Background}\label{bgsec}
We assume a standard background on graphs and hyperplane arrangements as given in \cite{Background}. We use \textit{graph} to mean an undirected finite graph without loops or multiple edges. For the rest of this section, let $G = ([n], E)$ be a graph. 

\begin{definition}\label{ChromaticPolynomial}
    The \emph{chromatic polynomial} of $G$, denoted by $\chi_G$, is the polynomial which when evaluated at a non-negative integer $q$ gives the number of proper $q$-colorings of $G$. 
\end{definition}

We now define \textit{source components} as in \cite{BN}. %Let $\ga$ be an acyclic orientation of $G$. For $i\in [n]$, let $R_i$ be the set of vertices reachable from $i$ by a directed path of $\ga$ (with $i \in R_i$). We define $S_1, S_2, \ldots$ recursively: for $k \geq 1$, if $\bigcup_{i < k} S_i = [n]$, then $S_k = \emp$. Otherwise, define $S_k = R_m \setminus \bigcup_{i < k} S_i$ where $m = \min\{[n] \setminus \bigcup_{i < k} S_i\}$.  
\begin{definition}\label{SourceComponents}
     Let $\ga$ be an acyclic orientation of $G$. For $i\in [n]$, let $R_i$ be the set of vertices reachable from $i$ by a directed path of $\ga$ (with $i \in R_i$). We define $S_1, S_2, \ldots$ recursively: for $k \geq 1$, if $\bigcup_{i < k} S_i = [n]$, then $S_k = \emp$. Otherwise, define $S_k = R_m \setminus \bigcup_{i < k} S_i$ where $m = \min\{[n] \setminus \bigcup_{i < k} S_i\}$.  The non-empty subsets $S_k$ thus defined are the \emph{source components} of $\gamma$.
\end{definition}

The following result was proved by Greene and Zaslavsky. 
\begin{theorem}\cite{GZ} \label{GZProj}
    Let $G = ([n], E)$ be a graph, and $k$ be a non-negative integer. Then, the coefficient of $(-1)^{n-k}q^k$ in $\chi_G(q)$ is the number of acyclic orientations of $G$ with exactly $k$ source components.  
\end{theorem}

The characteristic polynomial of a hyperplane arrangement $\mA$, denoted by $\chi_{\mA}$, is classically defined using the Mobius function of the intersection lattice. For our part, we use a characterization of the characteristic polynomial given by Lofano and Paolini~\cite{LP} and Kabluchko~\cite{Kabluchko}.

\begin{definition}
    Let $\mA$ be a hyperplane arrangement in $\R^n$ and let $v \in \R^n$ be an arbitrary point. Let $R$ be a region of $\mA$. We define the \emph{projection from $v$ to $R$} to be the unique point in $R$ that has the minimum Euclidean distance from $v$, and denote it by \emph{$\textup{proj}_v(R)$}. Further, we define the \emph{projection dimension of $v$ on $R$} to be the dimension of the unique face of $R$ that contains $\proj_v(R)$ in its interior, and denote it by $\pd_v(R)$.
\end{definition}

\begin{theorem}\cite{Kabluchko, LP}\label{Kab}
    Let $\mA$ be a real hyperplane arrangement in $\R^n$, and let $v \in \R^n$ be a generic point. Let $R(\mA)$ be the set of regions of $\mA$. 
    Then, the characteristic polynomial of $\mA$ is given by 
    $$\chi_{\mA}(t) = \sum\limits_{R \in R(\mA)} (-1)^{n - \pd_v(R)}t^{\pd_v(R)}.$$

    Equivalently, for a non-negative integer $k$, the coefficient of $(-1)^{n-k}t^k$ in $\chi_{\mA}(t)$ is the number of regions $R$ of $\mA$ such that the projection dimension of $v$ on $R$ is $k$.
\end{theorem}

\section{The Braid Arrangement}\label{braidsec}
In this section, we show that for the braid arrangement $\mB_n$, the projection statistic defined in \Cref{Kab} can be expressed as a combinatorial statistic on the permutations labeling the regions of $\mB_n$.

It is easy to see that each region of the braid arrangement is uniquely determined by a total ordering of the coordinates. As a consequence, there is a bijection between the regions of the braid arrangement $\mB_n$ and permutations of $[n]$. When considered in one line notation, the permutation indicates the relative order of the coordinates. For example, the permutation $\sigma = \sigma_1\sigma_2\ldots\sigma_n$ is associated to the region consisting of all points with coordinates $x_{\sigma_1} > x_{\sigma_2} > \ldots > x_{\sigma_n}$.

Moreover, the flats of the arrangement can be represented by partitions of $[n]$, the blocks indicating which coordinates are equal. Finally, the faces of the arrangement can be represented by ordered partitions of $[n]$, the relative order of the blocks indicating the relative order of the corresponding coordinates. Note that the number of blocks of the partition is the dimension of the corresponding face. Given a face $F$ of $\mA$, we denote by $\Pi(F)$ the ordered partition labeling it, and given an ordered partition $\Pi$ of $[n]$, we denote by $F_{\Pi}$ the face it labels. 

\begin{definition}\label{vector}
    Let $v \in \R^n$ with coordinates $(v_1, \ldots, v_n)$ such that $v_1 > \ldots > v_n$ and $v_i - v_{i+1} > n(v_{i+1} - v_n)$ for all $i < n$. For instance, $v_i = (n+1)^{-i}$ for all $i \in [n]$ defines such a point. 
\end{definition}

We now state the main result of this section. 
\begin{theorem}\label{braidRLmin}
    Let $v \in \R^n$ be as in \Cref{vector}, let $\sigma \in \Sn_n$ be a permutation and let $R_{\sigma}$ be the region of the braid arrangement $\mB_n$ labeled by $\sigma$. Then the projection dimension of $v$ on $R_{\sigma}$ equals the number of right-to-left minima of $\sigma$, that is, $\pd_v(R_{\sigma}) = \textup{RLmin}(\sigma)$. 
\end{theorem}
The rest of this section is dedicated to the proof of \Cref{braidRLmin}.
 
Let $v \in \R^n$ be as in \Cref{vector}, and $R$ be a region of $\mB_n$. There is a unique face of $R$ that contains $\proj_v(R)$ in its interior. In order to prove the above theorem, we first prove some lemmas which allow us to characterize this face. We state the following lemma without proof.
\begin{lemma}\label{projchar}
    Let $v \in \R^n$ and let $\Pi = \{B_1, \ldots, B_k\}$ be an unordered set partition of $[n]$. If $i \in B_j = \{j_1, \ldots, j_s\}$, then the projection of $v$ on the flat labeled by $\Pi$ has the $i^{\text{th}}$ coordinate given by $\frac{v_{j_1} + \ldots + v_{j_s}}{s}.$
\end{lemma}

\begin{definition}\label{goodface}
    Let $\mA$ be a hyperplane arrangement in $\R^n$, and let $v \in \R^n$ be a point. Let $F$ be a face of $\mA$. We say $F$ is a \emph{good face} if the projection of $v$ on span($F$) lies in the interior of $F$. 
\end{definition} 

The following lemma characterizes the good faces of $\mB_n$.
\begin{lemma}\label{GFCond}
    Let $v \in \R^n$ be as in \Cref{vector}, and let $\Pi = (B_1, \ldots, B_k)$ be an ordered partition of $[n]$. Then $F_{\Pi}$ is a good face of $\mB_n$ if and only if $\min(B_i) < \min(B_{i+1})$ for all $i < k$. 
\end{lemma}
\begin{proof} 
    Let $B = \{i_1, \ldots, i_k\}$ and $B' = \{i_1', \ldots, i_{\ell}'\}$ be two blocks of our partition, and write their values in increasing order. Then $\min(B) = i_1$ and $\min(B') = i_1'$. Without loss of generality, let $i_1 < i_1'$. Let $X = \text{span}(F_{\Pi})$, that is, $X$ is the flat labeled by the unordered partition $\{B_1, \ldots, B_k\}$. Let $\proj_v(X) = (p_1, \ldots, p_n)$. 

    Then, from \Cref{projchar} and the fact that $v$ satisfies \Cref{vector}, we have:
    \begin{align*}
        p_{i_1} - p_{i_1'} \geq \frac{(k-1)v_n + v_{i_1' - 1}}{k} - v_{i_1'}  \geq \frac{v_{i_1' - 1} - v_{i_1'} - n(v_{i_1'} - v_n)}{k}  > 0
    \end{align*}
    %Then, from \Cref{projchar}, and the fact that $v_{i_1} - v_{i_1' -1} + v_{i_2} - v_n + \ldots + v_{i_k} - v_n > 0$, we have: 
    %$$p_{i_1} = \frac{v_{i_1} + \ldots + v_{i_k}}{k} \geq \frac{(k-1)v_n + v_{i_1' - 1}}{k},$$
    %and, as $i_1' \leq i_j'$ for all $j \in [k]$, by choice of $v$, we have $v_{i_j'} \leq v_{i_1'}$, and hence,
    %$$p_{i_1'} = \frac{v_{i_1'} + \ldots + v_{i_{\ell'}}}{\ell} \leq v_{i_1'}.$$
    %This gives
    %\begin{align*}
    %    p_{i_1} - p_{i_1'} \geq \frac{v_{i_1' - 1} - v_{i_1'} - (k-1)(v_{i_1'} - v_n)}{k}
    %    > \frac{v_{i_1' - 1} - v_{i_1'} - n(v_{i_1'} - v_n)}{k}
    %    >0.
    %\end{align*}

    Hence $B$ must appear before $B'$ in the ordered partition.  
\end{proof}

\begin{lemma}\label{ProjOnGoodFace}
    Let $\mA$ be a hyperplane arrangement in $\R^n$, let $v \in \R^n$ be a point and let $R$ be a region of $\mA$.
    Then, $$\proj_v(R) = \proj_v(F)$$ where $F$ is a good face of $\mA$ incident to $R$.
\end{lemma}
\begin{proof}
    Clearly, there is a unique face $F$ of $R$ that contains $\proj_v(R)$ in its interior. Hence, $\proj_v(R) = \proj_v(F)$, and we need to show that $F$ is a good face. 

    Let $X = \s(F)$. Suppose $F$ is not a good face. Then, $\proj_v(X) \neq \proj_v(F)$. Let $L$ be the line joining $\proj_v(X)$ and $\proj_v(F)$. As $\proj_v(X)$ is the orthogonal projection of $v$ onto $X$ and $L$ lies in $X$, the distance between $v$ and a point $p \in L$ increases as $p$ moves from $\proj_v(X)$ to $\proj_v(F)$. But then $\proj_v(F)$ must be on the boundary of $F$ as otherwise we would have points on $L$ in $F$ closer to $v$, contradicting the fact that $\proj_v(F)$ minimizes distance. This contradicts the fact that $\proj_v(F)$ is in the interior of $F$, so $F$ must be a good face.
\end{proof}

\begin{figure}
    \centering
    \includegraphics[width=0.6\linewidth]{Fig1.pdf}
    \caption{$\mB_3$ with projection from a point $v$ as in \Cref{vector} onto the regions, with the regions labeled by permutations (in blue) with right-to-left minima marked by dots, and dimension of projection/number of right-to-left minima (in green).}
    \label{fig:enter-label}
\end{figure}
Now, we finally have enough information to prove \Cref{braidRLmin}.
\begin{proof}[Proof of \Cref{braidRLmin}]
    Let $\sigma = \sigma_1\ldots \sigma_n$, and let $F$ be a face of $R_{\sigma}$. Then, the ordered partition labeling $F$ is of the form $(\{\sigma_1, \ldots, \sigma_{i_1}\}, \{\sigma_{i_1 + 1}, \ldots, \sigma_{i_2}\}, \ldots, \{\sigma_{i_k + 1}, \sigma_{n}\})$ where $k \geq 0$, and $0 < i_1 < \ldots < i_{k}< n$. 

    Now, by \Cref{ProjOnGoodFace}, $\proj_v(R_{\sigma})$ must lie on a good face of $R_{\sigma}$. \Cref{GFCond} further gives us that these good faces are precisely those labeled by ordered partitions of $[n]$ of the form $\Pi = (B_1, \ldots, B_k)$ such that $\min(B_i) < \min(B_{i+1})$ for all $i < k$.

    This implies that if $F_{\Pi}$ is a good face of $R_{\sigma}$, then each block $B_i$ contains at least one right-to-left minimum. If not, suppose $j$ is the greatest index such that $B_j$ does not contain a right-to-left minimum. Then, $j<k$ and $\min(B_j) > \min(B_{j+1})$, contradicting that $F_{\Pi}$ is a good face. Hence, the dimension of a good face cannot be greater than \text{RLmin($\sigma$)}.

    Now, suppose that $F_{\sigma}$ is the face of $R_{\sigma}$ that $v$ projects into. If the dimension of $F_{\sigma}$ is less than RLmin($\sigma$), there is a block of $\Pi(F_{\sigma})$ that has more than one right-to-left minimum. We can refine the partition (by breaking this block into two blocks, each containing at least one right-to-left minimum) to get a partition corresponding to a larger face $F'$ which contains $F_\sigma$. This gives us the projection from $v$ onto $F'$ must be of shorter length (strictly shorter as $F'$ is a good face) than the projection onto $F_{\sigma}$, which is a contradiction. 

    Hence we have $\pd_v(R_{\sigma}) = \text{RLmin($\sigma$)}$.
\end{proof}

%In fact, the above theorem with \Cref{lbdim} gives us for $v \in \R^n$ as in \Cref{vector} with the additional condition that $v_1 \gg v_2 \gg \ldots \gg v_n$, the face of $R \in R(\mB_n)$ that $v$ projects into is precisely the he face labeled by the ordered partition obtained by partitioning $\sigma$ at its right-to-left minima, where $\sigma$ is the permutation labeling $R$. 
\section{Graphical Arrangements}\label{gasec}
Let $G = ([n], E)$ be a graph and $\mA_G$ be the corresponding graphical arrangement. 

\begin{definition}
    Let $R \in R(\mA_G)$. We associate to $R$ an acyclic orientation of $G$, denoted by $\gamma_R$, by directing the edge $\{i,j\} \in E$ towards $i$ if and only if $x_i \geq x_j$ in $R$. 
\end{definition}

\begin{lemma}\cite{BG2}
    The mapping $\gamma$ which associates to each region $R \in R(\mA_G)$ the orientation $\gamma_R$ is a bijection between $R(\mA_G)$ and the set of acyclic orientations of $G$. 
\end{lemma}

Recall that the faces of the braid arrangement can be identified with ordered partitions of $[n]$. As $\mA_G$ is a sub-arrangement of $\mB_n$, each flat of $\mA_G$ corresponds to a partition of $[n]$ and each face of $\mA_G$ corresponds to a set of ordered partitions of $[n]$. For a face $F$, we consider the representative ordered set partition where the blocks that do not have a relative order are ordered by increasing minimum elements, and denote it by $\Pi(F)$. 

Note that for an acyclic orientation $\gamma$ of $G$, the source components $(S_1, \ldots, S_k)$ of $\gamma$ form an ordered partiton of $[n]$. We denote this ordered partition by $\Pi(\gamma)$. 

\begin{definition}\label{vec2}
    Let $v \in \R^n$ with coordinates $(v_1, \ldots, v_n)$ such that $v_i > (6n^2 + 1)v_{i+1}$ and $v_n > 0$. For instance, $v_i = (6n^2 + 2)^{-i}$ for all $i \in [n]$ defines such a point. 
\end{definition}

Note that such a point $v \in \R^n$ will also satisfy the condition $v_i - v_{i+1} > n(v_{i+1} - v_n)$ for all $i < n$. Hence, any results that hold for a point $v$ as in \Cref{vector} will also hold for a point $v$ as in \Cref{vec2}.

The main result of this section is the following:
\begin{theorem}\label{graphSC}
     Let $G = ([n],E)$ be a graph and let $v$ be as in \Cref{vec2}. Let $R$ be a region of the graphical arrangement $\mA_G$, and let $\Pi(\gamma_R) = (B_1, \ldots, B_k)$. 

     Then, $\pd_v(R) = k$, that is, the projection dimension of $v$ on $R$ equals the number of source components of $\gamma_R$. In fact, the face of $R$ that $\proj_v(R)$ lies in the interior of is $F_{\Pi(\gamma_R)}$.
\end{theorem}

In the case of the braid arrangement, the above theorem along with the following lemma which we state without proof give us \Cref{braidRLmin}.
\begin{lemma}
    The number of right-to-left minima of a permutation $\sigma \in \Sn_n$ is equal to the number of source components of $\gamma_{R_{\sigma}}$, where $R_{\sigma}$ is the region of $\mB_n$ labeled by $\sigma$. 
\end{lemma}

Further, \Cref{graphSC} along with \Cref{Kab} and Equation~\eqref{CC} give us an alternative proof of Greene and Zaslavsky's result about the interpretation of the coefficients of the characteristic polynomial (\Cref{GZProj}).  

The rest of this section is devoted to the proof of \Cref{graphSC}.
\begin{lemma} \label{ubdim}
    Let $G = ([n], E)$ be a graph, let $R$ be a region of $\mA_G$, and let $\gamma_R$ be the acyclic orientation of $G$ labeling $R$. Let $\Pi(\gamma_R) = (B_1, \ldots, B_k)$. Then $F_{\Pi(\gamma_R)}$ is a good face of $R$ and $R$ does not have a good face of dimension greater than $k$. 
\end{lemma}
\begin{proof}
    Let $\Pi$ be an ordered partition of $[n]$. Then $\text{span}(F_{\Pi})$ is a flat of $\mA_G$ if and only if for every block $B$ of $\Pi$, the induced subgraph $G[B]$ is connected. This is because two coordinates $x_i$ and $x_j$ can be equated if and only if we have a set of hyperplanes $x_i = x_{k_1}$, $x_{k_1} = x_{k_2}$, \ldots, $x_{k_t} = x_j$, which corresponds to a path between $i$ and $j$ in $G$. 

    Further, $F_{\Pi}$ is a face of a region $R$ if and only if any weak inequality in $F_{\Pi}$ holds in $R$. Hence, it is clear that $F_{\Pi(\gamma_R)}$ is a face of $R$. Also, for $b_i = \min B_i$, we have $b_1 < b_2 < \ldots < b_k$, and hence $F_{\Pi(\gamma_R)}$ is a good face of $R$ by \Cref{GFCond}.

    Now, let $F'$ be a good face of $R$, and suppose $\Pi(F') = (D_1, \ldots, D_{\ell})$. 

    \noindent \textbf{Claim:} For all $j \in\{0\} \cup [k]$, $\bigcup\limits_{i = 1}^{j} B_i \sse \bigcup\limits_{i = 1}^{j}D_i$.

    We prove this using induction on $j \in [k]$. The base case for $j = 0$ is trivial. 

    Now, suppose we have $\bigcup\limits_{i = 1}^{j-1} B_i \sse \bigcup\limits_{i = 1}^{j-1}D_i$. Then two cases arise:

    \noindent \textbf{Case 1:} $b_j \in \bigcup\limits_{i = 1}^{j-1} D_i$.

    Let $m \in [n]$ be $b_j$-reachable. Then, $x_m > x_{b_j}$ for all $x \in R$. Now, if $m \in D_t$ for some $t \geq j$, we get $x_{b_j} > x_m$ for all $x \in R$, which is a contradiction. 

    Hence, $m \in \bigcup\limits_{i = 1}^{j-1} D_i$, which gives us $B_j \sse \bigcup\limits_{i = 1}^{j-1} D_i \sse \bigcup\limits_{i = 1}^{j} D_i$.

    \noindent \textbf{Case 2:} $b_j \notin \bigcup\limits_{i = 1}^{j-1} D_i$.

    Then $b_j \in D_j$ as if not, $b_j \in D_t$ for some $t > j$, which will give us $\min D_j > \min D_t$, contradicting the fact that $F'$ is a good face by \Cref{GFCond}. Further, as $b_j \in D_j$, we have $B_j \sse \bigcup\limits_{i = 1}^{j}D_i$ using the same argument as above. 

    Hence our claim is true by induction on $j$. 

    As $\bigcup\limits_{i = 1}^k B_i = [n]$, we have $[n] \sse \bigcup\limits_{i = 1}^k D_i$. So, $\ell \leq k$. 

    Thus $R$ does not have a good face of dimension greater than $k$. 
\end{proof}

\begin{lemma}\label{lbdim}
    Let $v$ be as in \Cref{vec2}. Let $R$ be a region of $\mA_G$, and let $\Pi(\gamma_R) = (B_1, \ldots, B_k)$. Let $p_B$ be the projection of $v$ onto $F_{\Pi(\gamma_R)}$. Let $\Pi' = (D_1, \ldots, D_{\ell}) \neq (B_1, \ldots, B_k)$, be such that $F_{\Pi'}$ is a good face of $R$ with $\ell \leq k$, and $p_D$ be the projection of $v$ onto $F_{\Pi'}$.  

    Then, $||p - p_B|| < ||p - p_D||$. 
\end{lemma}
\begin{proof}
    From \Cref{projchar}, $p_B = (p_1, \ldots, p_n)$, where $\forall i \in B_j$, $p_i = \sli_{m \in B_j} \dfrac{v_m}{|B_j|}$ and $p_D = (q_1, \ldots, q_n)$, where $\forall i \in D_j$, $q_i = \sli_{m \in D_j} \dfrac{v_m}{|D_j|}$.

    Now, from the proof \Cref{ubdim}, $B_1 = D_1$ or $B_1 \subsetneq D_1$, and if $B_i = D_i$ for all $i < j$, $B_j = D_j$ or $B_j \subsetneq D_j$. As $(D_1, \ldots, D_{\ell}) \neq (B_1, \ldots, B_k)$ we have $D_j \supsetneq B_j$ for some $j$. 

    Let $j$ be the first index where $D_j \supsetneq B_j$, let $|D_j| = d, |B_j| = b$, and let $\min(B_j) = b_j$. 
    
    %\begin{align*}
    %    ||v - p_B||^2 &= \sli_{i = 1}^k (v_i - p_i)^2 \\
    %    &=  \sli_{i \in B_m, m < j} (v_i - p_i)^2 + \sli_{i \in B_j}(v_i - p_i)^2 + \sli_{i \in B_m, m > j} (v_i - p_i)^2
        %&= \sli_{i \in B_m, m < j} (v_i - p_i)^2 + (v_{b_j} - p_{b_j})^2 + \sli_{\substack{i \in B_j \\ i \neq b_j}}(v_i - p_i)^2 + \sli_{i \in B_m, m > j} (v_i - p_i)^2
    %\end{align*}
    %Now,
    %\begin{align*}
    %    \sli_{i \in B_j}(v_i - p_i)^2 &=  \left(\frac{(b-1)}{b}v_{b_j} - \frac{1}{b}\sli_{\substack{i \in B_j \\ i \neq b_j}} v_i\right)^2 + \sli_{\substack{i \in B_j \\ i \neq b_j}}\left(\frac{v_{b_j}}{b} + \left(\sli_{\substack{\ell \in B_j \\ \ell \neq b_j}}\frac{v_{\ell}}{b} - v_i\right)\right)^2 \\
    %    &= \left(\frac{b-1}{b}\right)v_{b_j}^2 + \frac{(b-1)}{b^2}v_{b_j}^2 + \eps_1
    %\end{align*}
    %Further, taking $$\eps_2 = \sli_{i \in B_m, m > j} (v_i - p_i)^2,$$
    %for $\eps = \eps_1 + \eps_2$, we have 
    %$$|\eps| \leq \frac{1}{2n^2}v_{b_j}^2,$$
    %and hence,
    %\begin{align*}
    %    ||v - p_B||^2 
        %= \sli_{i \in B_m, m < j} (v_i - p_i)^2 + \left(\left(\frac{b-1}{b}\right)^2 + \frac{b-1}{b^2}\right)v_{b_j}^2 + \eps 
    %    \leq \sli_{i \in B_m, m < j} (v_i - p_i)^2 + \left(1 - \frac{1}{b}\right)v_{b_j}^2 + \frac{1}{2n^2}v_{b_j}^2
    %\end{align*}
    %In a similar manner, we get, %for an $|\eps'| \leq \frac{1}{2n^2}v_{b_j}^2$,
    %\begin{align*}
    %    ||v - p_D||^2 %= \sli_{i \in D_m, m < j} (v_i - p_i)^2 + \left(\left(\frac{d-1}{d}\right)^2 + \frac{d-1}{d^2}\right)v_{d_j}^2 + \eps' \\
    %    \geq \sli_{i \in D_m, m < j} (v_i - p_i)^2 + \left( 1- \frac{1}{d}\right)v_{b_j}^2 - \frac{1}{2n^2}v_{b_j}^2.
    %\end{align*}
    
    Then, as $v$ satisfies \Cref{vec2}, $B_i = D_i$ for all $i < j$, and $d > b$, we get
    \begin{align*}
       ||v - p_D||^2 - || v - p_B||^2 \geq \left(\frac{1}{b} - \frac{1}{d} - \frac{1}{n^2}\right)v_{b_j}^2 > 0. 
    \end{align*}
\end{proof}
\Cref{graphSC} is now a direct consequence of Lemmas~\ref{ubdim} and~\ref{lbdim}.

\section{Natural Unit Interval Graphs}\label{nuisec}
In this section, we consider a special type of graphs known as natural unit interval graphs. 

\begin{definition}
    A graph $G = ([n], E)$ is a \emph{natural unit interval graph} if for all $\{i,j\} \in E$, with $i<j$, we have for all $i < k < j$, $\{i,k\}\in E$ and $\{k,j\} \in E$. 
\end{definition}

We now consider the graphical arrangement $\mA_G$ of a natural unit interval graph $G$. We know that every region of the braid arrangement is indexed by a permutation. As a region of a graphical arrangement is a union of 
adjacent regions of the braid arrangement, each region $R$ of our graphical arrangement $\mA_G$ is uniquely associated to a set of permutations. Let us denote this set by $S_R$.

We now state the main results of this section:
\begin{theorem}\label{NUIProjRL}
    Let $G = ([n],E)$ be a natural unit interval graph, and let $R$ be a region of $\mA_G$. Let $\sigma\in \Sn_n$ be the lexicographic minimum of $S_R$. Let $v$ be as in \Cref{vec2}. Then, 
    $$\pd_v(R) = \emph{RLmin}(\sigma).$$
\end{theorem}

\begin{theorem}\label{NUIChar}
    Let $G = ([n], E)$ be a natural unit interval graph and $c_j = |\{i < j \mid \{i, j\} \in E\}|$ for all $j \in [n]$. Then, 
    $$\chi_{\mA_G}(q) = \prod\limits_{j = 1}^n (q - c_j).$$
\end{theorem}

The rest of this section is dedicated to the proof of Theorems~\ref{NUIProjRL} and ~\ref{NUIChar}. Note that \Cref{NUIChar} is known for the chromatic polynomial of a natural unit interval graph (see, for instance, \cite{NUI}).

\begin{definition}
    Let $G = ([n], E)$ be a natural unit interval graph. A permutation $\sigma = \sigma_1\ldots \sigma_n \in \Sn_n$ is said to be a \emph{$G$-local minimum} if for all $i \in [n-1]$ such that $\sigma_i > \sigma_{i+1}$, we have $\{\sigma_i, \sigma_{i+1}\} \in E$. 
\end{definition}

We now characterize $G$-local minima. To do this, we first define $G$-descents. 
\begin{definition}
     Let $G = ([n], E)$ be a natural unit interval graph and $\sigma = \sigma_1\ldots \sigma_n \in \Sn_n$. For $i \in [n-1]$ we say we have a \emph{$G$-descent} at $i$ (or that $\sigma_i\sigma_{i+i}$ is a \emph{$G$-descent}) if $\sigma_i > \sigma_{i+1}$ and $\{\sigma_i, \sigma_{i+1}\} \in E$. 
\end{definition}

From the definitions of $G$-local minima and $G$-descents, it is clear that for a natural unit interval graph $G$, a permutation $\sigma \in \Sn_n$ is a $G$-local minimum if and only if every descent of $\sigma$ is a $G$-descent. 
%and a region $R$ of the associated graphical arrangement $\mA_G$, a permutation $\sigma \in S_R$ is a $G$-local minimum of $S_R$ if and only if every descent of $\sigma$ is a $G$-descent. 
%Then, the following result is clear from the definitions of $G$-local minimum and $G$-descent.  
%\begin{lemma}\label{localminedgedesc}
%    Let $G = ([n], E)$ be a natural unit interval graph. Let $R$ be a region of the associated graphical arrangement $\mA_G$ and $S_R$ be the set of permutations associated to this region. Then, $\sigma \in S_R$ is a $G$-local minimum of $S_R$ if and only if every descent of $\sigma$ is a $G$-descent.  
%\end{lemma}
We further have:
\begin{lemma}\label{locallex}
    Let $G = ([n], E)$ be a natural unit interval graph. Let $R$ be a region of $\mA_G$ and let $S_R$ be the set of permutations associated to $R$. Then the unique $G$-local minimum permutation in $S_R$ is the lexicographic minimum of $S_R$. 
\end{lemma}
\begin{proof}
    Let $\sigma = \sigma_1\ldots \sigma_n$ be a $G$-local minimum in $S_R$ and $\tau = \tau_1 \ldots \tau_n$ be the lexicographic minimum of $S_R$. It is clear that $\tau$ is a $G$-local minimum as if there was a descent $\tau_i > \tau_{i+1}$ of $\tau$ such that $\{\tau_i, \tau_{i+1}\} \notin E$, we could swap $\tau_i$ and $\tau_{i+1}$ and get a permutation in $S_R$ that is less than $\tau$ in the lexicographic order. %lexicographically lesser than $\tau$. 
    
    We assume for contradiction that $\sigma \neq \tau$. Suppose they first differ at the $i^{\text{th}}$ position, that is, $\sigma_1 \ldots \sigma_{i-1} = \tau_1 \ldots \tau_{i-1}$ and $\sigma_i \neq \tau_i$. As $\tau$ is the lexicographic minimum, $\tau_i < \sigma_i$. Further, as they are permutations, $\tau_i = \sigma_k$ for some $k > i$. 

    Now, as both $\sigma$ and $\tau$ correspond to the same region of $\mA_G$, we can obtain one from the other by a sequence of swapping adjacent elements in the one line notation, where the pairs of swapped elements are of the form $\{a,b\}$ with $\{a,b\} \notin E$. 

    We have $\sigma = \tau_1\ldots \tau_{i-1} \sigma_{i}\ldots \sigma_{k-1}\tau_i \sigma_{k+1} \ldots \sigma_n$. To obtain $\tau$ from $\sigma$, we would have to swap $\tau_i$ with $\sigma_t$ for all $i \leq t \leq k-1$. Hence, for all $i \leq t \leq k-1$, $x_{\tau_i} = x_{\sigma_t}$ is not a hyperplane of $\mA_G$, that is, $\{\tau_i, \sigma_t\} \notin E$. 

    \noindent \textbf{Claim:} For $i \leq t \leq k-1$, we have $\sigma_t < \tau_i$.
        
     We prove this claim inductively. 

     Suppose $\sigma_{k-1} > \tau_i$. Then, $\sigma_{k-1}\tau_i$ is a descent which is not a $G$-descent, contradicting the fact that $\sigma$ is a $G$-local minimum. 

     Now, suppose for $r < t \leq k-1$, we have $\sigma_t < \tau_i$.

     Then, if $\sigma_r > \tau_i$, we have $\sigma_r > \sigma_{r+1}$. As $\sigma$ is a $G$-local minimum, we have $\{\sigma_r, \sigma_{r+1}\} \in E$. Further, as $G$ is a natural unit interval graph, we get that $\{\tau_i, \sigma_r\} \in E$, which is a contradiction. Hence, $\sigma_r < \tau_i$. 

     Hence our claim is proved.

     But then we have $\sigma_i < \tau_i$ which is a contradiction. Hence, $\sigma = \tau$, that is, a $G$-local minimum in $S_R$ is the lexicographic minimum of $S_R$ and hence is unique.  
\end{proof}

As the lexicographic minimum is unique for each region $R$ of $\mA_G$ where $G$ is a natural unit interval graph, we can choose the representative of the region $R$ to be the lexicographic minimum of $S_R$. In particular, these lexicographic minima will be precisely the permutations where all descents are $G$-descents. 

\begin{lemma}\label{lexfaceproj}
    Let $v$ be as in \Cref{vec2}, and let $G = ([n],E)$ be a natural unit interval graph. Let $R$ be a region of $\mA_G$. Then $\proj_v(R) \in R_{\sigma}$ where $\sigma$ is the lexicographic minimum of $S_R$, and $R_{\sigma}$ is the region of the braid arrangement $\mB_n$ labeled by $\sigma$. 
\end{lemma}
\begin{proof}
    Let $\sigma' \in S_R$ be such that $\proj_v(R) \in R_{\sigma'}$, where $R_{\sigma'}$ is the region of the braid arrangement $\mB_n$ labeled by $\sigma'$. Suppose $\sigma'$ is not the lexicographic minimum of $S_R$. Then, from \Cref{locallex}, we have that $\sigma'$ is not a $G$-local minimum. Hence for $\sigma' = \sigma_1'\ldots \sigma_n'$, we have for some $i \in [n]$, $\sigma_i' > \sigma_{i+1}'$ and $\{\sigma_i', \sigma_{i+1}'\} \notin E$. Then, $\sigma'' = \sigma_1'\ldots \sigma_{i+1}'\sigma_i'\ldots \sigma_n' \in S_R$. 

    Now, as a consequence of \Cref{braidRLmin} and \Cref{lbdim}, we have that the face $F'$ of $R_{\sigma'}$ that $v$ projects into is labeled by the ordered partition obtained by partitioning $\sigma'$ at the right-to-left minima. Let us denote this partition by $\Pi(F')$.  

    In $\Pi(F')$, $\sigma_i'$ and $\sigma_{i+1}'$ will be in the same block (as $\sigma_i'$ cannot be a right-to-left minimum). As swapping $\sigma_i'$ and $\sigma_{i+1}'$ does not affect the partition, $F'$ is a common face of $R_{\sigma'}$ and $R_{\sigma''}$. Hence $\proj_v(R) \in R_{\sigma''}$, the region of the braid arrangement $\mB_n$ labeled by $\sigma''$.  

    Continuing like this, we get that $\proj_v(R) \in R_{\sigma}$ where $\sigma$ is the $G$-local minimum of $S_R$ and hence the lexicographic minimum of $S_R$ by \Cref{locallex}, and $R_{\sigma}$ is the region of the braid arrangement $\mB_n$ labeled by $\sigma$. 
\end{proof}

%\begin{lemma}\label{braidface}
%    Let $v$ be as in \Cref{vec2}.
%    Let $i, j \in [n]$ with $i < j$ and $R_1$ and $R_2$ be two adjacent regions of the braid arrangement separated by the hyperplane $x_i = x_j$. Let $\sigma_1$ and $\sigma_2$ respectively be the permutations of the regions. Without loss of generality, let $\sigma_1 \preceq \sigma_2$ in lexicographic order. Then, on removing the hyperplane $x_i = x_j$, the projection of $v$ onto the merged region $R = R_1 \cup R_2$ lies on a face of $R_1$ that is also a face of $R$.
%\end{lemma}
%\begin{proof}
%    Now, as a consequence of \Cref{braidRLmin} and \Cref{lbdim}, we have for a region $R$ of the braid arrangement labeled by $\sigma \in \Sn_n$, the face that $v$ projects into is labeled by the ordered partition obtained by partitioning $\sigma$ at the right-to-left minima. 
    %Now, we have proven that given a region of the braid arrangement, the projection of $v$ lies on the face obtained by partitioning the permutation at the right-to-left minima. 

%    As $R_1$ and $R_2$ are adjacent regions separated by the hyperplane $x_i = x_j$, we have $\sigma_1 = w_1\ldots w_t i j w_{t+3} \ldots w_n$ and $\sigma_2 = w_1 \ldots w_t j i w_{t+3}\ldots w_n$. Now, let $F_1$ be the face that $v$ projects into of $R_1$ and $F_2$ the face that $v$ projects into of $R_2$. 

%    Note that the in $\Pi(F_2)$, $i$ and $j$ will always be in the same block, and swapping $i$ and $j$ will not affect this partition, that is, $F_2$ is a common face of $R_1$ and $R_2$. Hence, $v$ will project onto a face of $R_1$. What remains to show is that the face of $R_1$ it projects onto is not affected by the removal of the $x_i = x_j$ hyperplane. 

%    Now, two cases arise: 
    
%    Case 1: $i$ is not a right-to-left minimum of $\sigma_2$. 

%    Then, the ordered partition obtained on breaking up $\sigma_1$ and $\sigma_2$ at the right-to-left minima is the same. Let the minimum of the block containing $i$ and $j$ be $k$. Then, as $x_i = x_k$ and $x_k = x_j$ are still hyperplanes of the arrangement, $i$, $j$ and $k$ can still be in the same block of a ordered partition, that is, removing the $x_i = x_j$ hyperplane does not affect the corresponding face or its dimension. Hence $v$ projects onto a face of $R_1$. 

%    Case 2: $i$ is a right-to-left minimum of $\sigma_2$.

%    Then, in $\Pi(F_2)$, $i$ and $j$ are in the same block. Let $\Pi(F_2) = (B_1, \ldots, B_s, \ldots, B_t)$, with $i, j \in B_s$. 
%    However, two cases arise for $F_1$.

%    Subcase a: $j$ is a right-to-left minimum of $\sigma_1$. 

%    In this case, we get $\Pi(F_1) = (B_1, \ldots, B_s \setminus \{j\}, \{j\}, \ldots, B_t)$, that is, the dimension of $F_1$ is greater than the dimension of $F_2$. As $i$ and $j$ are in different blocks, $F_1$ is also a face of $R$. 

%    Subcase b: $j$ is not a right-to-left minimum of $\sigma_1$.

%    In this case, we get $\Pi(F_1) = (B_1, \ldots, B_s \setminus \{j\}, B_{s+1} \cup \{j\}, \ldots, B_t)$. As $i$ and $j$ are in different blocks, $F_1$ is also a face of $R$. 
%\end{proof}

%Now, we can obtain any natural unit interval graph $G = ([n], E)$ from $K_n$ by removing edges one at a time such that at each stage we have a natural unit interval graph. We can do this using the following procedure: 

%For $i \in [n]$, let $j_i \in [n]$ be the largest vertex that $i$ is adjacent to, that is, $i < j_i$, $\{i,j_i\} \in E$, but  $\{i, j_i+1\} \notin E$. Then, removing edges from $K_n$ in the order $\{1, n\}, \ldots, \{1, j_1 + 1\}, \{2, n\}, \ldots, \{2, j_2 + 1\}, \ldots, \{n-1, j_{n-1} + 1\}$ gives us a natural unit interval graph at every stage with the final graph being $G$. 

%Hence, we can induct on the number of edges in a natural unit interval graph. 
%\begin{lemma}\label{lexfaceproj}
%    Let $G = ([n], E)$ be a natural unit interval graph and $\mA_G$ be the corresponding hyperplane arrangement. Let $R$ be a region of $\mA_G$ and $\sigma$ the lexicographic least permutation associated to $R$. Then, the face of $R$ that $v$ projects onto is a face of the region of the braid arrangement corresponding to $\sigma$. 
%\end{lemma}
%\begin{proof}
%    The base case is proved in the previous lemma. 

%    Now, let $G' = ([n], E')$ be a natural unit interval graph and let $G = ([n], E)$ be a natural unit interval graph obtained by removing an edge $\{i,j\}$ from $G'$, where $i < j$.

%    Now, let $R_1$ and $R_2$ be two regions of $\mA_{G'}$ that get merged upon removing the $x_i = x_j$ hyperplane. 

%    Note that a permutation of the form $\sigma_1 = w_1\ldots w_t i j w_{t+3} \ldots w_n$ will be a representative of $R_1$ and $\sigma_2 = w_1\ldots w_t ji w_{t+3} \ldots w_n$ will be a representative of $R_2$. 

%    Claim: $\sigma_2$ is the lexicographic minimum permutation corresponding to region $R_2$. 

%    Suppose the claim is false. Let $\sigma_m = u_1\ldots u_t j u_{t+2} \ldots u_{t + k} i u_{t + k +2} \ldots u_n$ be the lexicographic minimum permutation corresponding to $R_2$ (we have $x_j > x_i$ in $R_2$, hence $j$ will appear before $i$ in any representative). 

%    Now, $u_{t + k} < j$, as if not, $u_{t+k}j$ is a descent and hence a $G$-descent. But then, as $i < j < u_{t + k}$, we have $\{i, j\} \in E$, a contradiction. 

%    Further, $u_{t+k} < i$, as if $i < u_{t+k} < j$, we would have $\{i, u_{t+k}\}$, $\{u_{t+k}, j\} \in E$. But then, we get that in any representative of $R_2$, $u_{t+k}$ must be between $j$ and $i$, contradicting the fact that $\sigma_2$ is a representative of $R_2$. 

%    Using a similar argument, we get that $u_{t+s} < i$ for all $2 \leq s \leq k$. 

%    But then, we have $ju_{t+2}$ is a descent and hence must be a $G$-descent, that is, $\{j, u_{t+2}\} \in E$. But, $u_{t+2} < i < j$ and the fact that $G$ is a natural unit interval graph gives us that $\{i, j\} \in E$, a contradiction. 

%    Hence $\sigma_2$ is the lexicographic minimum permutation corresponding to $R_2$ as claimed.

%    Now, by \Cref{braidface}, we know that between the regions corresponding to $\sigma_1$ and $\sigma_2$, $v$ projects onto a face of the region corresponding to $\sigma_1$. Further, by induction, the face of $R_1$ that $v$ projects onto is a face of the region of the braid arrangement corresponding to the lexicographic minimum of $R_1$. 

%    Hence, the face of $R$ that $v$ projects onto is a face of the region of the braid arrangement corresponding to $\sigma$. 
%\end{proof}

%Now, we also need to check that the dimension of the face that $v$ projects onto is not affected by the removal of hyperplanes. 

\begin{lemma}\label{faceexists}
    Let $G = ([n],E)$ be a natural unit interval graph, and let $R$ be a region of $\mA_G$. Let $\sigma\in \Sn_n$ be the lexicographic minimum of $S_R$. Let $\Pi$ be the ordered partition obtained by partitioning $\sigma$ at the right-to-left minima. Then, $F_{\Pi}$ is not contained in the interior of another face of $\mA_G$.
\end{lemma}
\begin{proof}
    To show that $F_{\Pi}$ is not contained in the interior of another face of $\mA_G$, it is enough to show that $\text{span($F_{\Pi}$)}$ is a flat of $\mA_G$. To show this, we show that for any block $B$ of $\Pi$, the induced subgraph $G[B]$ is connected. 
    
    Suppose the induced subgraph $G[B]$ is not connected. Let $i$ be the smallest vertex in $B$. As we get $\Pi$ by partitioning at the right-to-left minima, $i$ will appear after any other element of $B$ in the one line notation of $\sigma$. Let $j$ be the greatest vertex of the component with $i$, and $k$ be a vertex in a different component of the induced subgraph. 

    Now, as $i$ and $j$ are in the same component, we have a path from $i$ to $j$, say $ik_1k_2 \ldots k_t j$. Suppose we have $i < k < j$. Then, $k_s < k <k_{s+1}$ for some $s$ (take $k_0 = i$ and $k_{t+1} = j$). But, as $\{k_s, k_{s+1}\} \in E$, and $G$ is a natural unit interval graph, $\{k_s, k\} \in E$, that is, $k$ is in the same component as $k_s$ and hence the same component as $i$, a contradiction. 

    Hence $k > j$, that is, any other component of the induced subgraph has all vertices greater than $j$ and hence greater than any vertex in the component containing $i$. 
    We can order the components of $G[B]$ independently in the one line notation of $\sigma$ and still have a permutation in $S_R$. The permutation obtained by ordering these components such that the component with $i$ appears before any other component of $G[B]$ will be less than $\sigma$ in the lexicographic order. This contradicts the fact that $\sigma$ is the lexicographic minimum of $S_R$. Hence $G[B]$ is connected.      
    %Reordering the components of $G[B]$ in the one line notation of $\sigma$ gives us a permutation in $S_R$. Hence, the permutation where the component of $B$ with $i$ appears before the other components is in $S_R$. However, such a permutation will be lexicographically lesser than $\sigma$, contradicting the fact that $\sigma$ is the lexicographic minimum of $S_R$. Hence $G[B]$ is connected.  
    %As we can order the components independently, we can put the component with $i$ before the other components in the one line notation and get another permutation in $S_R$. However, this contradicts the fact that $\sigma$ is the lexicographic minimum. Hence $G[B]$ must be connected. 
\end{proof}
Hence, by Lemmas~\ref{lexfaceproj} and \ref{faceexists}, for a region $R \in R(\mA_G)$ and $v$ as in \Cref{vec2}, $\pd_v(R) = \text{dim($F_{\Pi}$)}$, where $\Pi$ is the ordered partition of $[n]$ obtained by partitioning the lexicographic minimum $\sigma$ of $S_R$ at its right-to-left minima. As $\dim(F_{\Pi})$ is clearly the number of right-to-left minima of $\sigma$, \Cref{NUIProjRL} follows. 
%As a consequence, if $\Pi$ is an ordered partition of $[n]$ obtained by partitioning a permutation $\sigma$ at its right-to-left minima, where $\sigma$ is the lexicographic minimum representative of a region $R \in R(\mA_G)$, we have the dimension of $F_{\Pi}$ is equal to the number of blocks of $\Pi$. As the number of blocks of $\Pi$ is the number of right-to-left minima of $\sigma$,  \Cref{NUIProjRL} is a consequence of Lemmas~\ref{lexfaceproj} and~\ref{faceexists}.

We can now obtain the characteristic polynomial of the graphical arrangement of a natural unit interval graph. 
\begin{proof}[Proof of \Cref{NUIChar}]
    From \Cref{NUIProjRL}, we have for a region $R$ of the graphical arrangement $\mA_G$, $\pd_v(R) = \text{RLmin($\sigma$)}$ where $\sigma$ is the lexicographic minimum of $S_R$. We have also shown that these lexicographic minima are precisely the permutations where all descents are $G$-descents. 

    Hence, from \Cref{Kab} we get that $$\chi_{\mA_G}(-q) = (-1)^n\sum\limits_{\substack{\sigma \in \Sn_n \\ \text{all descents of $\sigma$ are $G$-descents}} }q^{\text{RLmin($\sigma$)}}.$$

    So, it is enough to show that 
    
    $$\sum\limits_{\substack{\sigma \in \Sn_n \\ \text{all descents of $\sigma$ are $G$-descents}} }q^{\text{RLmin($\sigma$)}} = \prod\limits_{j = 1}^n (q + c_j).$$
    
    We prove this using induction on $n$. The base case is trivial.

    Suppose that the statement holds for a natural unit interval graph on $n-1$ vertices. 

    Let $G = ([n],E)$ be a natural unit interval graph and let $G' = G[n-1]$. Then $G'$ is also a natural unit interval graph. 

     Note that if we have a permutation of $[n]$ such that all descents are $G$-descents, removing $n$ gives us a permutation of $[n-1]$ such that all descents are $G$-descents. This is because for $\sigma = \sigma_1 \ldots \sigma_n$, with $\sigma_i = n$ ($i< n$), $n \sigma_{i+1}$ is a descent and hence a $G$-descent. If $\sigma_{i+1} < \sigma_{i-1}$, as $\{\sigma_{i+1}, n\} \in E$ and $G$ is a natural unit interval graph, we have $\{\sigma_{i+1},\sigma_{i-1}\} \in E$, and hence the only new descent formed on removing $n$ is a $G$-descent. If $\sigma_{i+1} > \sigma_{i - 1}$, no new descent is formed on removing $n$ and hence all descents are $G$-descents.  

    Hence, we can uniquely obtain all permutations of $[n]$  such that all descents are $G$-descents by inserting $n$ into a permutation of $[n-1]$ such that all descents are $G$-descents. There are two ways to do this:

    We can insert $n$ before any element it is adjacent to so that the descent thus formed is a $G$-descent. We have $c_n$ ways of doing this. In this case, the number of right-to-left minima of the permutation will remain the same as $n$ does not become a right-to-left minima and the ordering of the other elements is unchanged. The contribution of this to the characteristic polynomial will be $c_n\prod\limits_{j = 1}^{n-1} (q + c_j)$.

    We can also insert $n$ at the end of the permutation. This will not form any new descents, hence all descents will be $G$-descents. However, the number of right-to-left minima will increase by one as $n$ is also a right-to-left minima. The contribution of this to the characteristic polynomial will be $q\prod\limits_{j = 1}^{n-1} (q + c_j)$.

    Hence, we get that $\sum\limits_{\substack{\sigma \in \Sn_n \\ \text{all descents of $\sigma$ are $G$-descents}} }q^{\text{RLmin($\sigma$)}} = \prod\limits_{j = 1}^n (q + c_j)$.

    Hence, $\chi_{\mA_G}(-q) = (-1)^n\prod\limits_{j = 1}^n (q + c_j)$.
\end{proof}

\acknowledgements{I owe many thanks to Theo Douvropoulos for supplying the initial problem and some initial results (\Cref{braidRLmin} and Lemmas \ref{projchar} and \ref{GFCond}), and his guidance and suggestions. I also thank Olivier Bernardi for suggesting the extension to natural unit interval graphs and being a constant source of guidance throughout. In addition, I thank Vasiliy Neckrasov for his help with \Cref{lbdim}. Finally, I thank the reviewers for their suggestions.}

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



\end{document}
