\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage{tikz}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\usepackage[capitalise]{cleveref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\newcommand\Q{\mathbb{Q}}
\newcommand\R{\mathbb{R}}
\newcommand\Z{\mathbb{Z}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\ipa}{\mathrm{L}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
{\LARGE\bf Counting Regions of the \\
\vskip .1in
Boxed Threshold Arrangement}
\vskip 1cm
\large
Priyavrat Deshpande\footnote{Partially supported by a grant from the Infosys Foundation and the MATRICS grant MTR/2017/000239.},
Krishna Menon, and
Anurag Singh\footnote{Partially supported by a
grant from the Infosys Foundation.}\\
Chennai Mathematical Institute\\
H1, SIPCOT IT Park, Siruseri\\
Tamil Nadu 603103\\
India\\
\href{mailto:pdeshpande@cmi.ac.in}{\tt pdeshpande@cmi.ac.in}\\
\href{mailto:krishnamenon@cmi.ac.in}{\tt krishnamenon@cmi.ac.in}\\
\href{mailto:anuragsingh@cmi.ac.in}{\tt anuragsingh@cmi.ac.in}
\end{center}
\begin{abstract}
In this paper we consider the hyperplane arrangement in $\R^n$ whose hyperplanes are $\{x_i + x_j = 1\mid 1\leq i < j\leq n\}\cup \{x_i=0,1\mid 1\leq i\leq n\}$.
We call it the \emph{boxed threshold arrangement} since we show that the bounded regions of this arrangement are contained in an $n$-cube and are in one-to-one correspondence with
the labeled threshold graphs on $n$ vertices.
The problem of counting regions of this arrangement
was studied earlier by Song.
He determined the characteristic polynomial of this arrangement by relating its coefficients to the count of certain graphs.
Here, we provide bijective arguments to determine the number of regions.
In particular, we construct certain signed partitions of the set $\{-n,\dots, n\}\setminus\{0\}$ and also construct colored threshold graphs on $n$ vertices and show that both these objects are in bijection with the regions of the boxed threshold arrangement.
We independently count these objects and provide a closed form formula for the number of regions.
\end{abstract}
\section{Introduction}
A \emph{hyperplane arrangement} $\A$ is a finite collection of affine hyperplanes (i.e., codimension $1$ subspaces and their translates) in $\R^n$.
Without loss of generality we assume that arrangements we consider are \emph{essential}, i.e., the subspace spanned by the normal vectors is the ambient vector space.
Removing all the hyperplanes of $\A$ leaves $\R^n$ disconnected; counting the number of connected components using diverse combinatorial methods is an active area of research.
A \emph{flat} of $\A$ is a nonempty intersection of some of the hyperplanes in $\A$; the ambient vector space is a flat since it is an intersection of no hyperplanes.
Flats are naturally ordered by reverse set inclusion; the resulting poset is called the \emph{intersection poset} and is denoted by $\ipa(\A)$. A \emph{region} of $\A$ is a connected component of $\R^n\setminus \bigcup \A$.
The \emph{characteristic polynomial} of $\A$ is defined as
\[\chi_{\A}(t) := \sum_{x\in\ipa(\A)} \mu(\hat{0},x)\, t^{\dim(x)}\]
where $\mu$ is the M\"obius function of the intersection poset and $\hat{0}$ corresponds to the flat $\R^n$.
The characteristic polynomial is a fundamental combinatorial and topological invariant of the arrangement and plays a significant role throughout the theory of hyperplane arrangements. Among other things, the polynomial encodes enumerative information about the stratification of the space $\R^n$, induced by the arrangement.
We refer the reader to Stanley's notes \cite{stanarr07} for more on the enumerative aspects of hyperplane arrangements.
In particular we have the following seminal result by Zaslavsky.
\begin{theorem}[\cite{zas75}]
Let $\A$ be an arrangement in $\R^n$. Then the number of regions of $\A$ is given by
\[ r(\A) = (-1)^n \chi_{\A}(-1)\]
and the number of bounded regions is given by
\[b(\A) = (-1)^n \chi_{\A}(1). \]
\end{theorem}
The finite field method, developed by Athanasiadis \cite{athanas96}, converts the computation of the characteristic polynomial to a point counting problem.
A combination of these two results allowed for the computation of the number of regions of several arrangements of interest.
Another way to count the number of regions is to give a bijective proof.
This approach involves finding a combinatorially defined set whose elements are in bijection with the regions of the given arrangement and are easier to count.
For example, the regions of the braid arrangement (whose hyperplanes are given by the equations $x_i-x_j = 0$ for $1\leq i 0$ in $R$ where $i \neq j$ in $[n]$.
\item $i \succ_R \frac{1}{2}$ if $x_i > \frac{1}{2}$ in $R$ where $i \in [-n,n] \setminus \{0\}$.
\item Similarly define $i \prec_R \frac{1}{2}$, $i \succ_R -\frac{1}{2}$ and $i \prec_R -\frac{1}{2}$ for any $i \in [-n,n] \setminus \{0\}$.
\end{enumerate}
So $\prec_R$ is a relation on $[-n,n]\setminus \{0\} \cup \{-\frac{1}{2},\frac{1}{2}\}$ where comparable elements are
\begin{enumerate}
\item Elements of $[-n,n] \setminus \{0\}$ of different signs and different absolute values.
\item Elements of $[-n,n]\setminus \{0\}$ and $\pm \frac{1}{2}$.
\end{enumerate}
\begin{remark}
The reader can consider the relation $i \prec_R -j$ as $\overset{+}{i}$ appearing before $\overset{-}{j}$ in a signed permutation on $[n]$ and similarly for other such relations.
The equivalence defined in the following lemma corresponds to choosing a signed permutation representative for each region.
This is similar to the way Spiro \cite{spiro20} associated `threshold pairs in standard form' to labeled threshold graphs.
\end{remark}
\begin{lemma}\label{equi}
Let $\sim$ be the relation defined on the set $N=[-n,n]\setminus \{0\}$ as
$a \sim b$ if the following hold:
\begin{enumerate}
\item $a$ and $b$ are of the same sign, and
\item there does not exist any $c \in N \cup \{-\frac{1}{2},\frac{1}{2}\}$ such that $a \prec_R c \prec_R b$ or $b \prec_R c \prec_R a$.
\end{enumerate}
Then, $\sim$ is an equivalence relation on $N$.
\end{lemma}
\begin{proof}
It is clear that $a \sim a$ for any $a \in N$ and that $a \sim b$ implies that $b \sim a$ for any $a,b \in N$.
Let $a \sim b$ and $b \sim c$ for some distinct $a,b,c \in N$.
So $a,b,c$ are of the same sign.
By definition of $\prec_R$ and $\sim$, the only possible $d \in N \cup \{-\frac{1}{2},\frac{1}{2}\}$ such that $a \prec_R d \prec_R c$ is $-b$.
We must show that this is not possible (a similar argument works if $c \prec_R -b \prec_R a$).
Suppose $a \prec_R -b \prec_R c$.
We then have $-c \prec_R b \prec_R -a$.
If $a \prec_R -c$, we will have $a\prec_R -c \prec_R b$, which contradicts $a \sim b$.
So we must have $-c \prec_R a$.
But this gives $-a\prec_R c$ and hence $b \prec_R -a \prec_R c$, which is a contradiction to $b \sim c$.
Hence $\sim$ is an equivalence on $N$.
\end{proof}
\begin{definition}
The equivalence classes of $\sim$ defined in Lemma \ref{equi} will be called \textit{boxed threshold blocks} (corresponding to the region $R$).
Positive blocks refer to those blocks that contain positive numbers and similarly we define negative blocks.
\end{definition}
\begin{remark}
Since all the elements of a boxed threshold block are of the same sign, we sometimes consider a block as a subset of $[n]$ with a sign ($+$ or $-$) assigned to it.
\end{remark}
The proof of the following lemma follows from the definition of the equivalence.
\begin{lemma}
If $B$ is a boxed threshold block then so is $-B = \{ -b : b \in B\}$.
\end{lemma}
\begin{proposition}\label{totord}
Define an order $<$ on the set of boxed threshold blocks along with $\pm \frac{1}{2}$ as follows:
\begin{enumerate}
\item $B < B'$ where $B,B'$ are boxed threshold blocks if there exists a sequence $c_0,c_1,\dots,c_k$ of elements in $N \cup \{-\frac{1}{2},\frac{1}{2}\}$ such that $c_0 \prec_R c_1 \prec_R \cdots \prec_R c_k$, $c_0 \in B$ and $c_k \in B'$.
\item $-\frac{1}{2} < \frac{1}{2}$.
\item $B < \frac{1}{2}$ if $b \prec_R \frac{1}{2}$ for some $b \in B$. Similarly define other relations between blocks and $\pm \frac{1}{2}$.
\end{enumerate}
This is a total order in all cases except when there is a unique $i \in [n]$ such that $-\frac{1}{2} \prec_R i \prec_R \frac{1}{2}$.
\end{proposition}
\begin{proof}
The transitivity of this order is straightforward.
If we show that $B** 0$ if and only if the block containing $-j$ is before that containing $i$ and the relationship between $x_i$ and $\pm \frac{1}{2}$ is obtained in the same way.
On the other hand, given an order of one of the forms given above, choosing some real numbers $0< c_1 < c_2 < \cdots < c_k$ such that $c_i < \frac{1}{2}$ if $B_i < \frac{1}{2}$ and $c_i > \frac{1}{2}$ if $B_i > \frac{1}{2}$ and putting $x_a=c_i$ for all $a \in B_i$ for all $i \in [k]$, gives a point satisfying the required inequalities.
It can also be shown that different such orders correspond to different regions.
\end{proof}
Hence, to count the number of regions of $\mathcal{BT}_n$, we just have to count the number of orders of the forms mentioned in Proposition \ref{totord}.
Note that the first half of the order is the negative of the second, so we just consider the second half.
That is, we count orders of the following types, where in all cases, $B_1,\dots,B_k$ is a partition of $[n]$ with a sign assigned to each block:
\begin{enumerate}
\item $\frac{1}{2} < B_1 < B_2 < \cdots < B_k$ where $B_i$ and $B_{i+1}$ are of opposite signs for all $i \in [k-1]$.
\item $B_1 < \cdots < B_l < \frac{1}{2} < B_{l+1} < \cdots < B_k$ where the size of $B_1$ is greater than 1 and $B_i$ and $B_{i+1}$ are of opposite signs for all $i \in [l-1]$ and $i \in [l+1,k-1]$.
\item $B_1 < \frac{1}{2} < B_2 < \cdots < B_k$ where the size of $B_1$ is 1, $B_1$ and $B_2$ are of the same sign, and $B_i$ and $B_{i+1}$ are of opposite signs for all $i \in [2,k-1]$.
\end{enumerate}
\begin{proposition}\label{count}
The total number of orders of the forms mentioned above is
\begin{equation*}
4 \cdot a(n)+\sum_{k=1}^{n} 4 (k!-(k-1)!) (k \cdot S(n,k)-n \cdot S(n-1,k-1)).
\end{equation*}Here $a(n)$ is the $n^{th}$ ordered Bell number.
\end{proposition}
\begin{proof}
We will count the number of orders of each of the above forms.
\begin{enumerate}
\item In the first case, we just have to define an ordered partition of $[n]$ and assign alternating signs to them.
The number of ways this can be done is
\begin{equation*}
\sum_{k=1}^{n}\sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n}}2\cdot \dfrac{n!}{a_1!\cdots a_k!} = 2 \cdot a(n).
\end{equation*}
\item In the second case, we consider two sub-cases:
\begin{enumerate}
\item There is no block after $\frac{1}{2}$.
In this case, we have to define an ordered partition of $[n]$ whose first part has size greater that $1$ and assign alternating signs to them.
The number of ways this can be done is
\begin{equation*}
\sum_{k=1}^{n-1}\sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n,\ a_1 \neq 1}}2\cdot \dfrac{n!}{a_1!\cdots a_k!} = 2 (a(n) - n \cdot a(n-1))
\end{equation*}
where the equality is because the number of ordered partitions of $[n]$ with first block having size $1$ is $n \cdot a(n-1)$.
\item There is some block after $\frac{1}{2}$.
In this case, we have to again define an ordered partition of $[n]$ whose first part has size greater that $1$.
But we then have to choose a spot between two blocks to place $\frac{1}{2}$ and then choose a sign for the first block and the block after $\frac{1}{2}$.
The number of ways this can be done is
\begin{equation*}
\sum_{k=1}^{n-1}\sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n,\ a_1 \neq 1}}4 (k-1) \dfrac{n!}{a_1!\cdots a_k!}.
\end{equation*}Making the following substitution for all $k \in [n-1]$
\begin{align*}
\sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n,\ a_1 \neq 1}}\dfrac{n!}{a_1!\cdots a_k!} &= \sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n}}\dfrac{n!}{a_1!\cdots a_k!}\hspace{0.2cm} - \sum\limits_{\substack{(1,a_2,\dots,a_k)\\1+a_2+\cdots+a_k=n}}\dfrac{n!}{1!a_2!\cdots a_k!}\\[0.1cm]
&= k! \cdot S(n,k)-n \cdot (k-1)! \cdot S(n-1,k-1)
\end{align*}we get that the initial expression is the same as
\begin{equation*}
\sum_{k=1}^{n} 4 (k!-(k-1)!)(k \cdot S(n,k)-n \cdot S(n-1,k-1)).
\end{equation*}
\end{enumerate}
\item In the third case, we have to choose the element of $[n]$ in $B_1$ and then define an ordered partition of the remaining $(n-1)$ elements and assign alternating signs to them.
Since we want $B_1$ and $B_2$ to have the same sign, we just need to assign a sign to $B_2$.
So, the number of orders of the third type is
\begin{equation*}
n \cdot \sum_{k=1}^{n-1} \sum\limits_{\substack{(a_1,\dots,a_k)\\a_1+\cdots+a_k=n-1}}2\cdot \dfrac{(n-1)!}{a_1!\cdots a_k!} = n \cdot 2 \cdot a(n-1).
\end{equation*}
\end{enumerate}Adding up the counts made for each form gives us the required result.
\end{proof}
So, from the observations made above, we have proved the following theorem:
\begin{theorem}
The number of regions of $\mathcal{BT}_n$ is
\begin{align*}
4 \cdot a(n)+\sum_{k=1}^{n} 4 (k!-(k-1)!) (k \cdot S(n,k)-n \cdot S(n-1,k-1)).
\end{align*}
\end{theorem}
Similar arguments can be applied to the threshold arrangement $\mathcal{T}_n$.
\begin{proposition}\label{proposition:thresholdregions}
The regions of $\mathcal{T}_n$ are in bijection with ordered partitions of $[-n,n] \setminus \{0\}$ of the form
\begin{equation*}
-B_k < \cdots < -B_2 < -B_1 < B_1 < B_2 < \cdots < B_k
\end{equation*}where all elements of each block have the same sign, the size of $B_1$ is greater than $1$ and $B_i$ and $B_{i+1}$ are of opposite signs for all $i \in [k-1]$.
\end{proposition}
The bijection in Proposition \ref{proposition:thresholdregions} is defined just as was done for $\mathcal{BT}_n$.
That is, the region associated to such an order satisfies $x_i+x_j > 0$ if and only if $-j$ appears before $i$ in the order.
Again, such orders are completely specified by their second half, which are ordered partition of $[n]$ with first block size greater than $1$ and a sign assigned to the first block (and alternate signs for consecutive blocks).
So, we get the following theorem:
\begin{theorem}\label{theorem:counting of threshold regions}
The number of regions of $\mathcal{T}_n$ is
\begin{equation*}
2(a(n)-n \cdot a(n-1)).
\end{equation*}
\end{theorem}
\begin{remark}
It can be shown that the orders considered in \cref{proposition:thresholdregions} are in bijection with the set of threshold pairs (of size $n$) in standard form\footnote{A pair $(\pi, \omega)$ is a \emph{threshold pair} (of size $n$) if $\pi$ is a permutation of size $n$ and $\omega$ is a word in $\{+1,-1\}^n$. A threshold pair $(\pi, \omega)$ of size $n \geq 2$ is in \emph{standard form} if $\omega_1 = \omega_2$ and if $\omega_i = \omega_{i+1}$ implies $\pi_i < \pi_{i+1}$ for all $1 \leq i < n$.} considered by Spiro \cite{spiro20}.
In fact, he showed that the threshold pairs are in bijection with the labeled threshold graphs.
\end{remark}
The known formula for the number of labeled threshold graphs is in terms of Eulerian numbers.
Hence for the sake of completeness, we now show that the formula in \Cref{theorem:counting of threshold regions} is the same as the one containing Eulerian numbers.
We first recall a few identities related to Eulerian numbers $A(n,k)$ and the ordered Bell number $a(n)$.
A quick reference for these identities is B\'ona's book \cite[Section 1.1]{bonabook}.
\begin{itemize}
\item $a(n)=\sum\limits_{k=0}^{n-1} 2^k \cdot A(n,k)$
\item $A(n,0)=1$, $A(n,n-1)=1$ and $A(n,k)=0$ for all $k \geq n$.
\item $A(n,k)=(n-k) A(n-1,k-1)+(k+1) A(n-1,k)$ for $k\geq 1$.
\end{itemize}
\begin{proposition}
We have the following equality
\[r(\mathcal{T}_n) = \sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1).\]
\end{proposition}
\begin{proof}
\noindent From \cref{theorem:counting of threshold regions}, we have
\begin{equation*}
\begin{split}
r(\mathcal{T}_n) &= 2(a(n)-n \cdot a(n-1))\\
& = 2 \cdot \Bigg(\sum\limits_{k=0}^{n-1} 2^k \cdot A(n,k)- n \cdot \Big( \sum\limits_{k=0}^{n-2} 2^k \cdot A(n-1,k)\Big)\Bigg)\\
\frac{r(\mathcal{T}_n)}{2} & = A(n,0)+\sum\limits_{k=1}^{n-1} 2^k \big((n-k) A(n-1,k-1)+(k+1) A(n-1,k)\big)\\
& \hspace*{0.5cm}- n \Big( \sum\limits_{k=0}^{n-2} 2^k \cdot A(n-1,k)\Big) \\
& = \sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1) + \Big(A(n,0)+\sum\limits_{k=1}^{n-1} 2^k (k+1) A(n-1,k)\Big) \\
& \hspace*{0.5cm}- \sum\limits_{k=0}^{n-2} n \cdot 2^k \cdot A(n-1,k)
\end{split}
\end{equation*}
Since $A(n-1,n-1)=0$,
\begin{equation*}
\begin{split}
\frac{r(\mathcal{T}_n)}{2} & = \sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1) + \sum\limits_{k=0}^{n-2} 2^k (k+1) A(n-1,k)- \sum\limits_{k=0}^{n-2} n \cdot 2^k \cdot A(n-1,k)\\
&= \sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1) - \sum\limits_{k=0}^{n-2} (n-k-1) 2^k \cdot A(n-1,k)
\end{split}
\end{equation*}
Replacing $k+1$ by $t$ in the second sum, we get
\begin{equation*}
\begin{split}
r(\mathcal{T}_n) & = 2 \cdot \Bigg(\sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1) - \sum\limits_{t=1}^{n-1} 2^{t-1} (n-t) A(n-1,t-1)\Bigg)\\
& = \sum\limits_{k=1}^{n-1} 2^k (n-k) A(n-1,k-1).
\end{split}
\end{equation*}
\end{proof}
\section{The colored threshold graphs}\label{section4}
Before defining the colored threshold graphs that are in bijection with the regions of the boxed threshold arrangement, we recall the bijection between regions of the threshold arrangement and labeled threshold graphs.
\begin{definition}
A \textit{threshold graph} is defined recursively as follows:
\begin{enumerate}
\item The empty graph is a threshold graph.
\item A graph obtained by adding an isolated vertex to a threshold graph is a threshold graph.
\item A graph obtained by adding a vertex adjacent to all vertices of a threshold graph is a threshold graph.
\end{enumerate}
\end{definition}
\begin{definition}
A \textit{labeled threshold graph} is a threshold graph having $n$ vertices with vertices labeled distinctly using $[n]$.
\end{definition}
Such labeled threshold graphs can be specified by a signed permutation of $[n]$, that is, a permutation of $[n]$ with a sign associated to each number.
The signed permutation $i_1 i_2 \cdots i_n$ corresponds to the labeled threshold graph obtained by adding vertices labeled $|i_1|,|i_2|,\dots,|i_n|$ in order where a positive $i_k$ means that $|i_k|$ is added adjacent to all previous vertices and a negative $i_k$ means that it is added isolated to the previous vertices.
A maximal string of positive numbers or negative numbers in a signed permutation will be called a block.
\begin{example}
The labeled threshold graph associated to the signed permutation on $[5]$ given by $\overset{-}{2}\overset{-}{3}\overset{+}{1}\overset{+}{4}\overset{-}{5}$ is shown in Figure \ref{tgconst}.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (4) at (0.75,-2) {\small \color{white} 4};
\node at (1.5,0.5) {$\xrightarrow{\overset{-}{3}}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (4) at (0.75,-2) {\small \color{white} 4};
\node at (3.5,0.5) {$\xrightarrow{\overset{+}{1}}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (1) [circle,draw=black,inner sep=2pt] at (1,2) {\small $1$};
\node (4) at (0.75,-2) {\small \color{white} 4};
\node at (3.5,0.5) {$\xrightarrow{\overset{+}{4}}$};
\draw (3)--(1)--(2);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (1) [circle,draw=black,inner sep=2pt] at (1,2) {\small $1$};
\draw (3)--(1)--(2);
\node at (3.5,0.5) {$\xrightarrow{\overset{-}{5}}$};
\node (4) [circle,draw=black,inner sep=2pt] at (1,-2) {\small $4$};
\draw (1)--(4);
\draw (2)--(4);
\draw (3)--(4);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (1) [circle,draw=black,inner sep=2pt] at (1,2) {\small $1$};
\draw (3)--(1)--(2);
\node (4) [circle,draw=black,inner sep=2pt] at (1,-2) {\small $4$};
\node (5) [circle,draw=black,inner sep=2pt] at (3.5,0) {\small $5$};
\draw (1)--(4);
\draw (2)--(4);
\draw (3)--(4);
\end{tikzpicture}
\caption{Construction of threshold graph corresponding to $\overset{-}{2}\overset{-}{3}\overset{+}{1}\overset{+}{4}\overset{-}{5}$.}
\label{tgconst}
\end{figure}
\end{example}
The following facts can be verified:
\begin{enumerate}
\item The sign of the first number in the permutation does not matter and hence we can make the first block have size greater than 1.
\item Elements in the same block can be reordered.
\end{enumerate}
Hence, labeled threshold graphs can be specified by an ordered partition of $[n]$ with first block size greater than 1 and alternating signs assigned to the blocks.
In fact, this association is a bijection.
Given a threshold graph $G_1$, we can obtain this alternating signed ordered partition of $[n]$ as follows:
Since $G_1$ is a threshold graph, it has at least one isolated vertex or at least one vertex that is adjacent to all other vertices.
If it has an isolated vertex, set $D_1$ to be the set of all isolated vertices, assign it a negative sign and set $G_2$ to be the graph obtained by deleting all the vertices of $D_1$ from $G_1$.
If $G_1$ has at least one vertex adjacent to all other vertices, set $D_1$ to be the set of all such vertices, assign it a positive sign and set $G_2$ to be the graph obtained by deleting all the vertices of $D_1$ from $G_1$.
We repeat this process until we obtain a graph $G_k$ which is complete, in which case we set $D_k$ to be all vertices of $G_k$ and assign it a positive sign, or $G_k$ has no edges, in which case we set $D_k$ to be all vertices of $G_k$ and assign it a negative sign.
Then set $B_i=D_{k-i+1}$ and assign it the same sign as $D_{k-i+1}$ for all $i \in [k]$.
The signed ordered partition $B_1 , \dots, B_k$ is the one associated to $G_1$.
\begin{example} Figure \ref{tgdeconst} shows an example of obtaining the signed blocks from a threshold graph. The corresponding signed ordered partition for this example is $\overset{-}{\{2,3\}}\overset{+}{\{1,4\}}\overset{-}{\{5\}}$.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (1) [circle,draw=black,inner sep=2pt] at (1,2) {\small $1$};
\draw (3)--(1)--(2);
\node (4) [circle,draw=black,inner sep=2pt] at (1,-2) {\small $4$};
\node (5) [circle,draw=black,inner sep=2pt] at (3.5,0) {\small $5$};
\node at (5.5,0) {$\longrightarrow$};
\draw (1)--(4);
\draw (2)--(4);
\draw (3)--(4);
\node at (0.75,-3.5) {\color{white}$D_2=\overset{+}{\{1,4\}}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (1) [circle,draw=black,inner sep=2pt] at (1,2) {\small $1$};
\draw (3)--(1)--(2);
\node at (4,0) {$\longrightarrow$};
\node (4) [circle,draw=black,inner sep=2pt] at (1,-2) {\small $4$};
\draw (1)--(4);
\draw (2)--(4);
\draw (3)--(4);
\node at (0.75,-3.5) {$D_1=\overset{-}{\{5\}}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node (2) [circle,draw=black,inner sep=2pt] at (0,0) {\small $2$};
\node (3) [circle,draw=black,inner sep=2pt] at (2,0) {\small $3$};
\node (4) at (0.75,-2) {\small \color{white} 4};
\node at (4,0) {$\longrightarrow$};
\node at (0.75,-3.5) {$D_2=\overset{+}{\{1,4\}}$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.5]
\node at (0.75,-3.5) {$D_3=\overset{-}{\{2,3\}}$};
\end{tikzpicture}
\caption{Obtaining blocks from a threshold graph.}
\label{tgdeconst}
\end{figure}
\end{example}
Hence, regions of $\mathcal{T}_n$ and labeled threshold graphs on $n$ vertices are both in bijection with ordered partitions of $[n]$ with first block size greater than 1 and alternating signs assigned to the blocks.
Hence we obtain a bijection between regions of $\mathcal{T}_n$ and labeled threshold graphs on $n$ vertices.
By combining the definitions of the two bijections we see that to a labeled threshold graph on $n$ vertices we assign the region where $x_i+x_j > 0$ if and only if there is an edge between $i$ and $j$.
This can be proved as follows: If $-B_k < \cdots < -B_1 < B_1 < \cdots 0$ if and only if there is an edge between $i$ and $j$, $-\frac{1}{2} < x_i < \frac{1}{2}$ if $i$ is not colored, $x_i > \frac{1}{2}$ if $i$ is colored blue and $x_i<-\frac{1}{2}$ if $i$ is colored red.
Notice that the underlying labeled threshold graph corresponds to the $\mathcal{T}_n$ region that the $\mathcal{BT}_n$ region lies in.
Also, we can see that the bounded regions of $\mathcal{BT}_n$ are in bijection with the regions of $\mathcal{T}_n$.
Both are represented by labeled threshold graphs with $n$ vertices.
The bounded region of $\mathcal{BT}_n$ corresponding to a region of $\mathcal{T}_n$ is the one satisfying the same inequalities between $x_i+x_j$ and $0$ for all $i\neq j$ in $[n]$ and having $-\frac{1}{2} < x_i < \frac{1}{2}$ for all $i \in [n]$.
\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.4]
\draw (-4,10.5) node {\scriptsize $x_1=-\frac{1}{2}$};
\draw (4,10.5) node {\scriptsize $x_1=\frac{1}{2}$};
\draw (-11.6,-4) node {\scriptsize $x_2=-\frac{1}{2}$};
\draw (-11.35,4) node {\scriptsize $x_2=\frac{1}{2}$};
\draw (-10.5,10.5) node {\scriptsize $x_1+x_2=0$};
\draw (-4,10)--(-4,-10);
\draw (4,10)--(4,-10);
\draw (-10,4)--(10,4);
\draw (-10,-4)--(10,-4);
\draw (-10,10)--(10,-10);
\node (1) [circle,draw=black,inner sep=2pt] at (0,2.5) {\small 1};
\node (2) [circle,draw=black,inner sep=2pt] at (2.5,0) {\small 2};
\draw (1)--(2);
\node [circle,draw=black,inner sep=2pt] at (0,-2.5) {\small 2};
\node [circle,draw=black,inner sep=2pt] at (-2.5,0) {\small 1};
\node [circle,draw=black,fill=blue!10,inner sep=2pt] at (-6.5,5) {\small 2};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (-8.5,7) {\small 1};
\node [circle,draw=black,inner sep=2pt] at (-6,-1.5) {\small 2};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (-8.5,1) {\small 1};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (-6,-8.5) {\small 2};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (-8.5,-6) {\small 1};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (1,-8.5) {\small 2};
\node [circle,draw=black,inner sep=2pt] at (-1.5,-6) {\small 1};
\node [circle,draw=black,fill=red!10,inner sep=2pt] at (-6.5+13.75,-7-1.75) {\small 2};
\node [circle,draw=black,fill=blue!10,inner sep=2pt] at (-8.5+13.75,-5-1.75) {\small 1};
\node (1') [circle,draw=black,fill=red!10,inner sep=2pt] at (-6.5+13.75+1.75,-7) {\small 2};
\node (2') [circle,draw=black,fill=blue!10,inner sep=2pt] at (-8.5+13.75+1.75,-5) {\small 1};
\draw (1')--(2');
\node (1'')[circle,draw=black,inner sep=2pt] at (-6+14,-1.5) {\small 2};
\node (2'')[circle,draw=black,fill=blue!10,inner sep=2pt] at (-8.5+14,1) {\small 1};
\draw (1'')--(2'');
\node (a)[circle,draw=black,fill=blue!10,inner sep=2pt] at (-6+14,-1.5+7) {\small 2};
\node (b)[circle,draw=black,fill=blue!10,inner sep=2pt] at (-8.5+14,1+7) {\small 1};
\draw (a)--(b);
\node (a')[circle,draw=black,fill=blue!10,inner sep=2pt] at (-6+7,-1.5+7) {\small 2};
\node (b')[circle,draw=black,inner sep=2pt] at (-8.5+7,1+7) {\small 1};
\draw (a')--(b');
\node (c) [circle,draw=black,fill=blue!10,inner sep=2pt] at (-6.5+1.5,5+1.5) {\small 2};
\node (d) [circle,draw=black,fill=red!10,inner sep=2pt] at (-8.5+1.5,7+1.5) {\small 1};
\draw (c)--(d);
\end{tikzpicture}
\caption{Regions of $\mathcal{BT}_2$ represented by labeled colored threshold graphs}
\end{figure}
\section{Acknowledgments}
We express our thanks to the anonymous referee for helpful suggestions.
\begin{thebibliography}{12}
\bibitem{athanas96}
C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, \textit{Adv. Math.} {\bf 122} (1996), 193--233.
\bibitem{athanasiadis1999extended}
C. A. Athanasiadis, Extended Linial hyperplane arrangements for root systems and a conjecture of Postnikov and Stanley, \textit{J. Algebraic Combin.} {\bf 10} (1999), 207--225.
\bibitem{bonabook}
M. B\'{o}na, {\it Combinatorics of Permutations}, Second Edition, CRC Press, 2012.
\bibitem{OEIS}
N. J. A. Sloane et al., {\it The On-Line Encyclopedia of Integer Sequences},
2021. Available at \url{https://oeis.org}.
\bibitem{songenum17}
J. Song, Enumeration of graphs and the characteristic polynomial of the hyperplane arrangements $\mathcal{J}_n$, \textit{J. Korean Math. Soc.} {\bf 54} (2017), 1595--1604.
\bibitem{songcolor17}
J. Song, On certain hyperplane arrangements and colored graphs, \textit{Bull. Korean Math. Soc.} {\bf 54} (2017), 375--382.
\bibitem{songchar18}
J. Song, Characteristic polynomial of the hyperplane arrangements $\mathcal{J}_n$ via finite field method, \textit{Commun. Korean Math. Soc.} {\bf 33} (2018), 759--765.
\bibitem{spiro20}
S. Spiro, Counting labeled threshold graphs with Eulerian numbers, \textit{Australas. J. Combin.} {\bf 77} (2020), 249--255.
\bibitem{stanarr07}
R. P. Stanley, An introduction to hyperplane arrangements, in E. Miller, V. Reiner, and B. Sturmfels, eds., {\em Geometric Combinatorics}, Amer. Math. Soc., 2007, pp.~389--496.
\bibitem{zas75}
T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, {\em Mem. Amer. Math. Soc.} {\bf 1} (1975), No.~154.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 52C35 Secondary 32S22, 05C30, 11B68.
\noindent \emph{Keywords:} threshold graph, hyperplane arrangement, finite field method.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A005840},
\seqnum{A039757}, and
\seqnum{A341769}.)
\bigskip
\hrule
\vspace*{+.1in}
\noindent
Received February 3 2021;
revised versions received February 19 2021; February 21 2021.
Published in {\it Journal of Integer Sequences}, April 26 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**