Counting Regions of the Boxed Threshold Arrangement

Priyavrat Deshpande^{1}, Krishna Menon, and Anurag Singh^{2} Chennai Mathematical Institute H1, SIPCOT IT Park, Siruseri Tamil Nadu 603103 India

                 pdeshpande@cmi.ac.in
                krishnamenon@cmi.ac.in
                 anuragsingh@cmi.ac.in

Abstract

In this paper we consider the hyperplane arrangement in ℝ^{n} whose hyperplanes are {x_{i} + x_{j} = 1 | 1 ≤ i < j ≤ n} ∪ {x_{i} = 0, 1 | 1 ≤ i ≤ n}. We call it the 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, …, n} \ {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.

1 Introduction

A hyperplane arrangement A is a finite collection of affine hyperplanes (i.e., codimension 1 subspaces and their translates) in ℝ^{n}. Without loss of generality we assume that arrangements we consider are essential, i.e., the subspace spanned by the normal vectors is the ambient vector space. Removing all the hyperplanes of A leaves ℝ^{n} disconnected; counting the number of connected components using diverse combinatorial methods is an active area of research. A 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 intersection poset and is denoted by L(A). A region of A is a connected component of ℝ^{n} \ ⋃ A. The characteristic polynomial of A is defined as

1Partially supported by a grant from the Infosys Foundation and the MATRICS grant MTR/2017/000239.

2Partially supported by a grant from the Infosys Foundation.

χ_{A}(t) := ∑_{x∈L(A)} μ(ˆ0, x) t^{dim(x)}

where μ is the Möbius function of the intersection poset and ˆ0 corresponds to the flat ℝ^{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 ℝ^{n}, induced by the arrangement. We refer the reader to Stanley’s notes [9] for more on the enumerative aspects of hyperplane arrangements. In particular we have the following seminal result by Zaslavsky.

Theorem 1 ([10]). Let A be an arrangement in ℝ^{n}. Then the number of regions of A is given by

r(A) = (−1)^{n}χ_{A}(−1)

and the number of bounded regions is given by

b(A) = (−1)^{n}χ_{A}(1).

The finite field method, developed by Athanasiadis [1], 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 ≤ i < j ≤ n) correspond to the n! permutations of order n. The regions of the Shi arrangement (whose hyperplanes are given by the equations x_{i} − x_{j} = 0, 1 for 1 ≤ i < j ≤ n) are in bijection with the parking functions on [n], hence the number of regions is (n + 1)^{n−1}. Refer to Stanley’s notes [9, Lecture 5] for details.

In the present article we consider the following hyperplane arrangement

BT_{n} := {X_{i} + X_{j} = 1 | 1 ≤ i < j ≤ n} ∪ {X_{i} = 0, 1 | 1 ≤ i ≤ n}.

The problem of counting regions of this arrangement was recently solved by Song in a series of papers. His first approach [6, 5] involved relating the coefficients of the characteristic polynomial to the generating functions for the number of certain graphs. These generating functions [5, Theorem 1] have quite a complicated expression and consequently make it difficult to determine a compact form for the characteristic polynomial. Later Song [7] used the finite field method to get a slightly simpler expression for the characteristic polynomial.

The main aim of this paper is to provide bijective proofs for the number of regions of this arrangement. In particular, in Section 3 we construct certain (signed) ordered partitions of the set {−n, −(n−1), …, n−1, n}\{0} and show that they are in bijection with the regions of BT_{n}. We also show how to count these partitions. In Section 4 we spell out a recipe to color the vertices of a labeled threshold graph on n vertices such that the number of such colored threshold graphs is equal to the regions of BT_{n}. However, we begin the article by establishing a simpler form for the characteristic polynomial in Section 2. There we also justify the term “boxed threshold”.

2 The characteristic polynomial

We first translate the hyperplanes in BT_{n} in order to obtain a combinatorially isomorphic arrangement with the same characteristic polynomial. Putting X_{i} = x_{i} + \frac{1}{2} for every i we get

\{x_{i} + x_{j} = 0 | 1 ≤ i < j ≤ n\} ∪ \{x_{i} = −\frac{1}{2}, \frac{1}{2} | 1 ≤ i ≤ n\}.  (1)

We will stick to the notation BT_{n} to denote the above arrangement. The notation [k] is used to denote the set {1, …, k}. We begin by stating a generalization of the finite field method, given by Athanasiadis [2], in our context.

Theorem 2 ([2, Theorem 2.1]). If A is a sub-arrangement of the type C arrangement in ℝ^{n}, that is, a sub-arrangement of {x_{i} ± x_{j} = 0 | 1 ≤ i < j ≤ n} ∪ {x_{i} = 0 | i ∈ [n]}, there exists an integer k such that for all odd integers q greater than k,

χ_{A}(q) = #(ℤ_{q}^{n} \ V_{A})

where V_{A} is the union of hyperplanes in ℤ_{q}^{n} obtained by reducing A mod q.

We use this result to prove the following relationship between the characteristic polynomial of sub-arrangements of the type C arrangement and that of their “boxed” versions.

Proposition 3. Let A be an arrangement in ℝ^{n} that is a sub-arrangement of the type C arrangement and let BA = A ∪ \{x_{i} = −\frac{1}{2}, \frac{1}{2} | i ∈ [n]\}. Then

χ_{BA}(t) = χ_{A}(t − 2).

Proof. Let q be any large odd number. Set D_{q}^{n} := \{(a_{1}, …, a_{n}) ∈ ℤ_{q}^{n} | a_{i} ≠ ±\frac{q−1}{2}\}. Define a bijection f : ℤ_{q−2} → ℤ_{q} \ \{\frac{q−1}{2}, −\frac{q−1}{2}\} as

f(i) = i for i ∈ [−\frac{q − 3}{2}, \frac{q − 3}{2}].

It is clear that for any a, b ∈ ℤ_{q−2} 1. a + b = 0 ⇔ f(a) + f(b) = 0,

2. a − b = 0 ⇔ f(a) − f(b) = 0, and

3. a = 0 ⇔ f(a) = 0.

Using f, we can define a bijection F : ℤ_{q−2}^{n} → D_{q}^{n} as

F (a_{1}, …, a_{n}) = (f(a_{1}), …, f(a_{n})) for (a_{1}, …, a_{n}) ∈ ℤ_{q−2}^{n}.

By the properties of f, we can see that F induces a bijection between those tuples in ℤ_{q−2}^{n} that do not satisfy the defining equation of any hyperplane in A and those tuples in ℤ_{q}^{n} that do not satisfy the defining equation of any hyperplane in BA. So, we get that for large odd numbers q,

χ_{BA}(q) = χ_{A}(q − 2).

Since χ_{BA} and χ_{A} are polynomials, we get the required result.

Let T_{n} denote the threshold arrangement in ℝ^{n}, i.e., T_{n} := {x_{i} + x_{j} = 0 | 1 ≤ i < j ≤ n}. The reason this is called the threshold arrangement is that its regions are in bijection with labeled threshold graphs on n vertices (see Section 4 for details). This is clearly a subarrangement of the type C arrangement.

Corollary 4. The characteristic polynomials of BT_{n} and T_{n} are related as follows:

χ_{BT_{n}}(t) = χ_{T_{n}}(t − 2).

Consequently, the number of bounded regions of BT_{n} is equal to the number of regions of T_{n}. Moreover, these bounded regions are contained in the cube (or a box) [−\frac{1}{2}, \frac{1}{2}]^{n}. Next, we derive a closed form expression for χ_{T_{n}}(t) using the finite field method.

Proposition 5. The characteristic polynomial of the threshold arrangement T_{n} is

χ_{T_{n}}(t) = ∑_{k=1}^{n}(S(n, k) + n · S(n − 1, k)) ∏_{i=1}^{k}(t − (2i − 1)).

Here S(n, k) are the Stirling numbers of the second kind.

Proof. Using Theorem 2, we see that the characteristic polynomial of T_{n} satisfies, for large odd values of q,

χ_{T_{n}}(q) = |{(a_{1}, …, a_{n}) ∈ ℤ_{q}^{n} | a_{i} + a_{j} ≠ 0 for all 1 ≤ i < j ≤ n}|.

This means that we need to count the functions f : [n] → ℤ_{q} such that

1. |f^{−1}(0)| ≤ 1.

2. f can take at most one value from each of the sets

\{1, −1\}, \{2, −2\}, …, \{\frac{q − 1}{2}, −\frac{q − 1}{2}\}.

We split the count into the two cases. If 0 is not attained by f, then all values must be from

\{1, −1\} ∪ \{2, −2\} ∪ ⋯ ∪ \{\frac{q − 1}{2}, −\frac{q − 1}{2}\}.

with at most one value attained in each set. So, there are

\binom{\frac{q−1}{2}}{k} · 2^{k} · k! · S(n, k)

ways for f to attain values from exactly k of these sets. This is because we have \binom{\frac{q−1}{2}}{k} · 2^{k} ways to choose the k sets and which element of each set f should attain and k!S(n, k) ways to choose the images of the elements of [n] after making this choice. So the total number of f such that 0 is not attained is

∑_{k=1}^{n} \binom{\frac{q−1}{2}}{k} · 2^{k} · k! · S(n, k).

When 0 is attained, there are n ways to choose which element of [n] gets mapped to 0 and using a similar logic for choosing the images of the other elements, we get that the total number of f where 0 is attained is

n · ∑_{k=1}^{n−1} \binom{\frac{q−1}{2}}{k} · 2^{k} · k! · S(n − 1, k).

So we get that for large q,

χ_{T_{n}}(q) = ∑_{k=1}^{n} \binom{\frac{q−1}{2}}{k} · 2^{k} · k! · S(n, k) + n · ∑_{k=1}^{n−1} \binom{\frac{q−1}{2}}{k} · 2^{k} · k! · S(n − 1, k)

= ∑_{k=1}^{n}(S(n, k) + n · S(n − 1, k)) ∏_{i=1}^{k}(q − (2i − 1)).

Since χ_{T_{n}} is a polynomial, we get the required result.

Remark 6. Note that the absolute value of the coefficient of t^{j} in (t−1)(t−3) ⋯ (t−(2k−1)) counts the number of signed permutations on [k] with j odd cycles (see \underline{A039757} in the OEIS [4]). Let us denote that number by a(k, j). Using this we get a compact expression for the coefficient of t^{j} in χ_{T_{n}}(t) as

∑_{k=j}^{n}(S(n, k) + n · S(n − 1, k))a(k, j).

Corollary 7. The coefficient of t^{j} in χ_{BT_{n}}(t) is

∑_{k=j}^{n}(S(n, k) + n · S(n − 1, k))b(k, j).

where b(k, j) is the coefficient of t^{j} in (t − 3)(t − 5) ⋯ (t − (2k + 1)).

Proof. Using Corollary 4 we get

χ_{BT_{n}}(t) = ∑_{k=1}^{n}(S(n, k) + n · S(n − 1, k)) ∏_{i=1}^{k}(t − (2i + 1)).

Expanding the product gives us the required expression. Note that b(k, j) = − ∑_{i=0}^{j} a(k + 1, i)

where a(k, j) is defined in Remark 6.

Remark 8. We can also derive an expression for the exponential generating function for the characteristic polynomial. Using Problem 25(c) in Stanley’s notes [9, Lecture 5] we get

∑_{n≥0} χ_{BT_{n}}(t)\frac{x^{n}}{n!} = (1 + x)(2e^{x} − 1)^{\frac{(t−3)}{2}} .

The generating function for the number of regions is

∑_{n≥0} r(BT_{n})\frac{x^{n}}{n!} = \frac{e^{2x}(1 − x)}{(2 − e^{x})^{2}}.

For the sake of completeness we enumerate the coefficients of the characteristic polynomial for smaller values of n (see Table 1). Song [5] also computed the characteristic polynomial for n ≤ 10, however there are typos in all the expressions for n ≥ 4, consequently the region numbers are wrong. The sequence of number of regions of BT_{n} can be found at the entry \underline{A341769} in the OEIS [4].

3 The signed ordered partitions

In this section we prove a bijection between regions of BT_{n}, and certain ordered partitions of [−n, n]\\{0\}∪\{−\frac{1}{2}, \frac{1}{2}\} (the notation [−n, n] is used for the set \{−n, −n+1, …, n−1, n\}). We will denote −x_{i} by x_{−i} for all i ∈ [n]. Let R be a region of BT_{n}. We write

1. i ≺_{R} −j if x_{i} + x_{j} < 0 in R where i ≠ j in [n].

2. i ≻_{R} −j if x_{i} + x_{j} > 0 in R where i ≠ j in [n].

\begin{matrix}n & χ_{BT_{n}}(t) & r(BT_{n}) \\ 2 & t^{2} − 5t + 6 & 12 \\ 3 & t^{3} − 9t^{2} + 27t − 27 & 64 \\ 4 & t^{4} − 14t^{3} + 75t^{2} − 181t + 165 & 436 \\ 5 & t^{5} − 20t^{4} + 165t^{3} − 695t^{2} + 1480t − 1263 & 3624 \\ 6 & t^{6} − 27t^{5} + 315t^{4} − 2010t^{3} + 7320t^{2} − 14284t + 11559 & 35516 \\ 7 & {t^{7} − 35t^{6} + 546t^{5} − 4865t^{4} + 26460t^{3} − 87010t^{2} + 158753t − \atop 122874} & 400544 \\ 8 & {t^{8}−44t^{7}+882t^{6}−10402t^{5}+78155t^{4}−379666t^{3}+1154965t^{2}− \atop 1995487t + 1486578} & 5106180 \\ 9 & {t^{9} − 54t^{8} + 1350t^{7} − 20286t^{6} + 200025t^{5} − 1331022t^{4} + \atop 5932143t^{3} − 16952157t^{2} + 27979203t − 20158695} & 72574936 \\ 10 & t^{10} − 65t^{9} + 1980t^{8} − 36840t^{7} + 459585t^{6} − 3986031t^{5} + ; 24172575t^{4} − 100548090t^{3} + 272771475t^{2} − 432836011t + ; 302751327 & 1137563980 \end{matrix}

Table 1: Characteristic polynomial and the number of regions of BT_{n} for n ≤ 10.

3. i ≻_{R} \frac{1}{2} if x_{i} > \frac{1}{2} in R where i ∈ [−n, n] \ \{0\}.

4. Similarly define i ≺_{R} \frac{1}{2}, i ≻_{R} −\frac{1}{2} and i ≺_{R} −\frac{1}{2} for any i ∈ [−n, n] \ \{0\}. So ≺_{R} is a relation on [−n, n] \ \{0\} ∪ \{−\frac{1}{2}, \frac{1}{2}\} where comparable elements are

1. Elements of [−n, n] \ {0} of different signs and different absolute values.

2. Elements of [−n, n] \ \{0\} and ±\frac{1}{2}. Remark 9. The reader can consider the relation i ≺_{R} −j as i^{+} appearing before 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 [8] associated ‘threshold pairs in standard form’ to labeled threshold graphs. Lemma 10. Let ∼ be the relation defined on the set N = [−n, n] \ {0} as

a ∼ b if the following hold:

1. a and b are of the same sign, and

2. there does not exist any c ∈ N ∪ \{−\frac{1}{2}, \frac{1}{2}\} such that a ≺_{R} c ≺_{R} b or b ≺_{R} c ≺_{R} a. Then, ∼ is an equivalence relation on N.

Proof. It is clear that a ∼ a for any a ∈ N and that a ∼ b implies that b ∼ a for any a, b ∈ N. Let a ∼ b and b ∼ c for some distinct a, b, c ∈ N. So a, b, c are of the same sign. By definition of ≺_{R} and ∼, the only possible d ∈ N ∪ \{−\frac{1}{2}, \frac{1}{2}\} such that a ≺_{R} d ≺_{R} c is −b. We must show that this is not possible (a similar argument works if c ≺_{R} −b ≺_{R} a). Suppose a ≺_{R} −b ≺_{R} c. We then have −c ≺_{R} b ≺_{R} −a. If a ≺_{R} −c, we will have a ≺_{R} −c ≺_{R} b, which contradicts a ∼ b. So we must have −c ≺_{R} a. But this gives −a ≺_{R} c and hence b ≺_{R} −a ≺_{R} c, which is a contradiction to b ∼ c. Hence ∼ is an equivalence on N.

Definition 11. The equivalence classes of ∼ defined in Lemma 10 will be called boxed threshold blocks (corresponding to the region R). Positive blocks refer to those blocks that contain positive numbers and similarly we define negative blocks.

Remark 12. 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.

The proof of the following lemma follows from the definition of the equivalence.

Lemma 13. If B is a boxed threshold block then so is −B = {−b : b ∈ B}.

Proposition 14. Define an order < on the set of boxed threshold blocks along with ±\frac{1}{2} as follows:

1. B < B′ where B, B′ are boxed threshold blocks if there exists a sequence c_{0}, c_{1}, …, c_{k} of elements in N ∪ \{−\frac{1}{2}, \frac{1}{2}\} such that c_{0} ≺_{R} c_{1} ≺_{R} ⋯ ≺_{R} c_{k}, c_{0} ∈ B and c_{k} ∈ B′.

2. −\frac{1}{2} < \frac{1}{2}.

3. B < \frac{1}{2} if b ≺_{R} \frac{1}{2} for some b ∈ B. Similarly define other relations between blocks and ±\frac{1}{2}.

This is a total order in all cases except when there is a unique i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}.

Proof. The transitivity of this order is straightforward. If we show that B < B is not possible for any block, the order is well-defined. Suppose c_{0} ≺_{R} c_{1} ≺_{R} ⋯ ≺_{R} c_{k} where c_{0}, c_{k} ∈ B. If c_{1} ≠ −c_{k} we get a contradiction to c_{0} ∼ c_{k} and similarly if c_{k−1} ≠ −c_{1}. So we must have c_{1} = −c_{k} and c_{k−1} = −c_{1}. But then we get c_{1} ≺_{R} −c_{k} and −c_{1} ≺_{R} c_{k}, which is a contradiction.

We will now show that this order is a total order in all cases except when there is unique i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}. The relationship of any block with ±\frac{1}{2} is always defined. So we only have to check that any two blocks are comparable. Let B, B′ be boxed threshold blocks. If B, B′ are distinct blocks of the same sign, they are comparable by definition of the equivalence relation. If they are of opposite sign and not of the form {i}, {−i} for some i ∈ [n], they are comparable since there is some a ∈ B and b ∈ B′ of opposite signs such that |a| ≠ |b|. So we have to deal with the case B = {i} and B′ = {−i} for some i ∈ [n]. If i ≻_{R} \frac{1}{2} or i ≺_{R} −\frac{1}{2}, \{−i\} and \{i\} are comparable.

Suppose −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2} and \{i\} and \{−i\} are blocks and they are not comparable. We have already seen that all the positive blocks are comparable and so are all the negative blocks. Let the order on the positive blocks be B_{1} < B_{2} < ⋯ < B_{k} and hence the order on the negative blocks is −B_{k} < ⋯ < −B_{2} < −B_{1}.

Suppose B_{1} = \{i\}. Since i is not the only number satisfying −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}, we have b ≺_{R} \frac{1}{2} for all b ∈ B_{2}. Taking some b ∈ B_{2}, since i ∉ B_{2}, there is some k ∈ [n] such that i ≺_{R} −k ≺_{R} b. Since {−i} is a block, and k ≠ i, there is some l ∈ [n] such that −i ≺_{R} l ≺_{R} −k (we cannot have −k ≺_{R} l ≺_{R} −i since this would mean {i} and {−i} are comparable). But this gives k ≺_{R} −l ≺_{R} i, which contradicts the fact that there is no positive block less than {i}. We get a similar contradiction if B_{k} = {i}.

Suppose B_{m} = {i} for some m ∈ [2, k − 1]. Take some b_{p} ∈ B_{m−1} and b_{s} ∈ B_{m+1}. There are three possibilities:

1. There are k_{p}, k_{s} ∈ [n] such that

b_{p} ≺_{R} −k_{p} ≺_{R} i ≺_{R} −k_{s} ≺_{R} b_{s}.

Since k_{p}, k_{s} ≠ i, and {−i} is a block, there are c_{p}, c_{s} ∈ [n] such that

−k_{p} ≺_{R} c_{p} ≺_{R} −i
−i ≺_{R} c_{s} ≺_{R} −k_{s}

where the other possibilities are not possible since {i} and {−i} are not comparable. So we get

b_{p} ≺_{R} −k_{p} ≺_{R} c_{p} ≺_{R} −i ≺_{R} c_{s} ≺_{R} −k_{s} ≺_{R} b_{s}.

But this means that c_{p} and c_{s} are in blocks between B_{m−1} and B_{m+1} and hence in {i}, which is a contradiction.

2. There is no k_{s} ∈ [n] such that i ≺_{R} −k_{s} < b_{s}. So we must have i ≺_{R} \frac{1}{2} ≺_{R} b_{s}, −\frac{1}{2} ≺_{R} b_{p} ≺_{R} \frac{1}{2} and k_{p} ∈ [n] such that

b_{p} ≺_{R} −k_{p} ≺_{R} i ≺_{R} \frac{1}{2} ≺_{R} b_{s}.

This is because i satisfies −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2} and is not the only such number. Since k_{p} ≠ i, and {−i} is a block, there is some c_{p} ∈ [n] such that

−k_{p} ≺_{R} c_{p} ≺_{R} −i

where the other possibility is not possible since {i} and {−i} are not comparable. So we get

−\frac{1}{2} ≺_{R} b_{p} ≺_{R} −k_{p} ≺_{R} c_{p} ≺_{R} −i

which, along with previous observations, gives

i ≺_{R} −c_{p} ≺_{R} k_{p} ≺_{R} \frac{1}{2} ≺_{R} b_{s}.

But this means k_{p} is in a positive block after {i} but before B_{m+1}, which is a contradiction.

3. The case when there is no k_{p} ∈ [n] such that b_{p} ≺_{R} −k_{p} ≺_{R} i is handled similarly.

In the case when there is unique i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}, the only order that is not defined is between the blocks {i} and {−i} and the order is of the form

− B_{k} < ⋯ < −B_{2} < −\frac{1}{2} < \{i\}, \{−i\} < \frac{1}{2} < B_{2} < ⋯ < B_{k}  (2)

where B_{2}, …, B_{k} are blocks (not necessarily positive). This can be proved using similar arguments as before.

If there is a unique i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2} and the blocks are ordered as in (2), we make the convention that {−i} < {i} if B_{2} is a positive block and {i} < {−i} if B_{2} is a negative block. Once this convention is made, we get a total order on the boxed threshold blocks, \frac{1}{2} and −\frac{1}{2} in all cases. The proof of the following lemma follows from the definition of the order.

Lemma 15. For any blocks B, B′, B < B′ implies that −B′ < −B. Similarly, other usual properties of taking the negative hold; such as B < \frac{1}{2} implies that −\frac{1}{2} < −B.

Proposition 16. The total order associated to a region (defined in Proposition 14) is always of one of the following forms:

1. −B_{k} < ⋯ < −B_{2} < −B_{1} < −\frac{1}{2} < \frac{1}{2} < B_{1} < B_{2} < ⋯ < B_{k} where B_{i} and B_{i+1} are of opposite signs for all i ∈ [k − 1].

2. −B_{k} < ⋯ < −B_{l+1} < −\frac{1}{2} < −B_{l} < ⋯ < −B_{1} < B_{1} < ⋯ < B_{l} < \frac{1}{2} < B_{l+1} < ⋯ < 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 ∈ [l − 1] and i ∈ [l + 1, k − 1].

3. −B_{k} < ⋯ < −B_{2} < −\frac{1}{2} < −B_{1} < B_{1} < \frac{1}{2} < B_{2} < ⋯ < 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 ∈ [2, k − 1].

The association of such an order is a bijection between the regions of BT_{n} and total orders of the types mentioned above.

Proof. The fact that the first half of the order is the negative of the second follows from Lemma 15. By the definition of blocks, for any two blocks of the same sign which are in the same position with respect to ±\frac{1}{2}, there is some block of opposite sign between them.

The first form is when there is no i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}. The third form is by the convention we made at the end of the proof of Proposition 14, when there is a unique i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}.

So we have to show that when there is more than one i ∈ [n] such that −\frac{1}{2} ≺_{R} i ≺_{R} \frac{1}{2}, the block B_{1} has size greater than 1. Suppose B_{1} = {a} for some a ∈ N. Let b ∈ B_{2}. b has the same sign as −a and is in a different block. Hence there is some k ∈ N of opposite sign to −a and b such that −a ≺_{R} k ≺_{R} b. But this means k is in a block between {−a} and B_{2} and hence in {a}, which is a contradiction since k ≠ a.

We will now show that the association of such an order is a bijection between the regions of BT_{n} and total orders of the types mentioned above. First note that, from the total order associated to a region, we can get back the inequalities describing the region as follows: For any i ≠ j in [n], x_{i} + x_{j} > 0 if and only if the block containing −j is before that containing i and the relationship between x_{i} and ±\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} < ⋯ < 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 ∈ B_{i} for all i ∈ [k], gives a point satisfying the required inequalities. It can also be shown that different such orders correspond to different regions.

Hence, to count the number of regions of BT_{n}, we just have to count the number of orders of the forms mentioned in Proposition 14. 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}, …, B_{k} is a partition of [n] with a sign assigned to each block:

1. \frac{1}{2} < B_{1} < B_{2} < ⋯ < B_{k} where B_{i} and B_{i+1} are of opposite signs for all i ∈ [k − 1].

2. B_{1} < ⋯ < B_{l} < \frac{1}{2} < B_{l+1} < ⋯ < 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 ∈ [l − 1] and i ∈ [l + 1, k − 1].

3. B_{1} < \frac{1}{2} < B_{2} < ⋯ < 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 ∈ [2, k − 1].

Proposition 17. The total number of orders of the forms mentioned above is

4 · a(n) + ∑_{k=1}^{n} 4(k! − (k − 1)!)(k · S(n, k) − n · S(n − 1, k − 1)).

Here a(n) is the n^{th} ordered Bell number.

Proof. We will count the number of orders of each of the above forms.

1. 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

∑_{k=1}^{n} ∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n \end{matrix}} 2 · \frac{n!}{a_{1}! ⋯ a_{k}!} = 2 · a(n).

2. In the second case, we consider two sub-cases:

(a) 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

∑_{k=1}^{n−1} ∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n, a_{1}≠1 \end{matrix}} 2 · \frac{n!}{a_{1}! ⋯ a_{k}!} = 2(a(n) − n · a(n − 1))

where the equality is because the number of ordered partitions of [n] with first block having size 1 is n · a(n − 1).

(b) 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

∑_{k=1}^{n−1} ∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n, a_{1}≠1 \end{matrix}} 4(k − 1)\frac{n!}{a_{1}! ⋯ a_{k}!}.

Making the following substitution for all k ∈ [n − 1]

∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n, a_{1}≠1 \end{matrix}} \frac{n!}{a_{1}! ⋯ a_{k}!} = ∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n \end{matrix}} \frac{n!}{a_{1}! ⋯ a_{k}!} − ∑_{\begin{matrix}(1,a_{2},...,a_{k}) \\ 1+a_{2}+···+a_{k}=n \end{matrix}} \frac{n!}{1!a_{2}! ⋯ a_{k}!}

= k! · S(n, k) − n · (k − 1)! · S(n − 1, k − 1)

we get that the initial expression is the same as

∑_{k=1}^{n} 4(k! − (k − 1)!)(k · S(n, k) − n · S(n − 1, k − 1)).

3. 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

n · ∑_{k=1}^{n−1} ∑_{\begin{matrix}(a_{1},...,a_{k}) \\ a_{1}+···+a_{k}=n−1 \end{matrix}} 2 · \frac{(n − 1)!}{a_{1}! ⋯ a_{k}!} = n · 2 · a(n − 1).

Adding up the counts made for each form gives us the required result.

So, from the observations made above, we have proved the following theorem:

Theorem 18. The number of regions of BT_{n} is

4 · a(n) + ∑_{k=1}^{n} 4(k! − (k − 1)!)(k · S(n, k) − n · S(n − 1, k − 1)).

Similar arguments can be applied to the threshold arrangement T_{n}.

Proposition 19. The regions of T_{n} are in bijection with ordered partitions of [−n, n] \ {0} of the form

−B_{k} < ⋯ < −B_{2} < −B_{1} < B_{1} < B_{2} < ⋯ < B_{k}

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 ∈ [k − 1].

The bijection in Proposition 19 is defined just as was done for 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:

Theorem 20. The number of regions of T_{n} is

2(a(n) − n · a(n − 1)).

Remark 21. It can be shown that the orders considered in Proposition 19 are in bijection with the set of threshold pairs (of size n) in standard form^{3} considered by Spiro [8]. In fact, he showed that the threshold pairs are in bijection with the labeled threshold graphs.

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 Theorem 20 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óna’s book [3, Section 1.1].

3A pair (π, ω) is a threshold pair (of size n) if π is a permutation of size n and ω is a word in {+1, −1}^{n}.

A threshold pair (π, ω) of size n ≥ 2 is in standard form if ω_{1} = ω_{2} and if ω_{i} = ω_{i+1} implies π_{i} < π_{i+1} for all 1 ≤ i < n.

• a(n) = ∑_{k=0}^{n−1} 2^{k} · A(n, k)

• A(n, 0) = 1, A(n, n − 1) = 1 and A(n, k) = 0 for all k ≥ n.

• A(n, k) = (n − k)A(n − 1, k − 1) + (k + 1)A(n − 1, k) for k ≥ 1. Proposition 22. We have the following equality

r(T_{n}) = ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1).

Proof. From Theorem 20, we have

r(T_{n}) = 2(a(n) − n · a(n − 1))

= 2 · ( ∑_{k=0}^{n−1} 2^{k} · A(n, k) − n · ( ∑_{k=0}^{n−2} 2^{k} · A(n − 1, k)))

\frac{r(T_{n})}{2} = A(n, 0) + ∑_{k=1}^{n−1} 2^{k}((n − k)A(n − 1, k − 1) + (k + 1)A(n − 1, k))

− n( ∑_{k=0}^{n−2} 2^{k} · A(n − 1, k))

= ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1) + (A(n, 0) + ∑_{k=1}^{n−1} 2^{k}(k + 1)A(n − 1, k))

− ∑_{k=0}^{n−2} n · 2^{k} · A(n − 1, k)

Since A(n − 1, n − 1) = 0,

\begin{aligned}\frac{r(T_{n})}{2} & = ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1) + ∑_{k=0}^{n−2} 2^{k}(k + 1)A(n − 1, k) − ∑_{k=0}^{n−2} n · 2^{k} · A(n − 1, k) \\ & = ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1) − ∑_{k=0}^{n−2}(n − k − 1)2^{k} · A(n − 1, k) \end{aligned}

Replacing k + 1 by t in the second sum, we get

\begin{aligned}r(T_{n}) & = 2 · ( ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1) − ∑_{t=1}^{n−1} 2^{t−1}(n − t)A(n − 1, t − 1)) \\ & = ∑_{k=1}^{n−1} 2^{k}(n − k)A(n − 1, k − 1). \end{aligned}

4 The colored threshold graphs

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.

Definition 23. A threshold graph is defined recursively as follows:

1. The empty graph is a threshold graph.

2. A graph obtained by adding an isolated vertex to a threshold graph is a threshold graph.

3. A graph obtained by adding a vertex adjacent to all vertices of a threshold graph is a threshold graph.

Definition 24. A labeled threshold graph is a threshold graph having n vertices with vertices labeled distinctly using [n].

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} ⋯ i_{n} corresponds to the labeled threshold graph obtained by adding vertices labeled |i_{1}|, |i_{2}|, …, |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.

Example 25. The labeled threshold graph associated to the signed permutation on [5] given

by 2^{−}3^{−}1^{+}4^{+}5^{−} is shown in Figure 1.

2 4 ⟶^{3^{−}}  ^{2 3 4 ⟶^{1^{+}}}  ^{2 3 1 4 ⟶^{4^{+}}}  ^{2 3 1 ⟶^{5^{−}} 4}  2 3 1 4 5
Figure 1: Construction of threshold graph corresponding to 2^{−}3^{−}1^{+}4^{+}5^{−}.

The following facts can be verified:

1. 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.

2. Elements in the same block can be reordered.

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 ∈ [k]. The signed ordered partition B_{1}, …, B_{k} is the one associated to G_{1}.

Example 26. Figure 2 shows an example of obtaining the signed blocks from a threshold

graph. The corresponding signed ordered partition for this example is {2, 3}^{−}{1, 4}^{+}{5}^{−}.

2 3 1 4 5⟶ D_{2} = {1, 4}^{+}  ^{2 3 1⟶ 4D_{1} = {5}^{−}}  ^{2 3 4⟶ D_{2} = {1, 4}^{+}}  D_{3} = {2, 3}^{−}

Figure 2: Obtaining blocks from a threshold graph.

Hence, regions of 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 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} < ⋯ < −B_{1} < B_{1} < ⋯ < B_{k} is the threshold block order corresponding to some region R of T_{n}, −j ≺_{R} i for some i ≠ j in [n] if and only if one of the following holds:

1. −j and i both appear in B_{1}, …, B_{k} with −j appearing first.

2. −j appears in −B_{k}, …, −B_{1} and i appears in B_{1}, …, B_{k}.

3. −j and i both appear in −B_{k}, …, −B_{1} with −j appearing first.

Equivalently, one of the following holds:

1. −j and i both appear in B_{1}, …, B_{k} with −j appearing first.

2. i and j both appear in B_{1}, …, B_{k}.

3. −i and j both appear in B_{1}, …, B_{k} with −i appearing first.

But this is precisely the condition for there to be an edge between i and j in the threshold graph corresponding to B_{1} < ⋯ < B_{k}.

We now move on to the boxed threshold arrangement.

Definition 27. A colored threshold graph is defined recursively as follows:

1. The empty graph is a colored threshold graph.

2. A graph obtained by adding an isolated vertex to a colored threshold graph is a colored threshold graph. If there are colored vertices in the initial colored threshold graph, the new vertex should be colored red. If not, the new vertex can be left uncolored or colored red.

3. A graph obtained by adding a vertex adjacent to all vertices of a colored threshold graph is a colored threshold graph. If there are colored vertices in the initial colored threshold graph, the new vertex should be colored blue. If not, the new vertex can be left uncolored or colored blue.

Definition 28. A labeled colored threshold graph is a colored threshold graph with n vertices with the vertices labeled distinctly with elements of [n].

Just as for threshold graphs, labeled colored threshold graphs can be represented as a signed permutation. However, we also have to specify if and when the coloring of the vertices starts. This is done by using the symbol \frac{1}{2}. Having \frac{1}{2} at the end of the signed permutation means that none of the vertices should be colored.

Example 29. The sequence 2^{+} \frac{1}{2} 1^{+}3^{+}4^{−}5^{−} corresponds to the graph shown in Figure 3.

2 1 3 4 5

Figure 3: Labeled colored threshold graph corresponding to 2^{+} \frac{1}{2} 1^{+}3^{+}4^{−}5^{−}.

Using similar observations about these sequences associated to labeled colored threshold graphs as done for labeled threshold graphs, we get that labeled colored threshold graphs are in bijection with orders of the forms counted in Proposition 17. Since these orders also correspond to region of BT_{n}, we get a bijection between labeled colored threshold graphs with n vertices and regions of BT_{n}. Just as before, the inequalities describing the region associated to a colored threshold graph are as follows: x_{i} + x_{j} > 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 T_{n} region that the BT_{n} region lies in.

Also, we can see that the bounded regions of BT_{n} are in bijection with the regions of T_{n}. Both are represented by labeled threshold graphs with n vertices. The bounded region of BT_{n} corresponding to a region of T_{n} is the one satisfying the same inequalities between x_{i} + x_{j} and 0 for all i ≠ j in [n] and having −\frac{1}{2} < x_{i} < \frac{1}{2} for all i ∈ [n].

\begin{matrix}x_{1} = − \frac{1}{2} \\ x_{1} = \frac{1}{2} \\ x_{2} = − \frac{1}{2} \\ x_{2} = \frac{1}{2} \\ x_{1} + x_{2} = 0 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \\ 2 \\ 1 \end{matrix}

Figure 4: Regions of BT_{2} represented by labeled colored threshold graphs

5 Acknowledgments

We express our thanks to the anonymous referee for helpful suggestions.

References

[1] C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math. 122 (1996), 193–233.

[2] C. A. Athanasiadis, Extended Linial hyperplane arrangements for root systems and a conjecture of Postnikov and Stanley, J. Algebraic Combin. 10 (1999), 207–225.

[3] M. Bóna, Combinatorics of Permutations, Second Edition, CRC Press, 2012.

[4] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

   at https://oeis.org.

[5] J. Song, Enumeration of graphs and the characteristic polynomial of the hyperplane arrangements J_{n}, J. Korean Math. Soc. 54 (2017), 1595–1604.

[6] J. Song, On certain hyperplane arrangements and colored graphs, Bull. Korean Math. Soc. 54 (2017), 375–382.

[7] J. Song, Characteristic polynomial of the hyperplane arrangements J_{n} via finite field method, Commun. Korean Math. Soc. 33 (2018), 759–765.

[8] S. Spiro, Counting labeled threshold graphs with Eulerian numbers, Australas. J. Combin. 77 (2020), 249–255.

[9] R. P. Stanley, An introduction to hyperplane arrangements, in E. Miller, V. Reiner, and B. Sturmfels, eds., Geometric Combinatorics, Amer. Math. Soc., 2007, pp. 389–496.

[10] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. 1 (1975), No. 154.

2010 Mathematics Subject Classification: Primary 52C35 Secondary 32S22, 05C30, 11B68. Keywords: threshold graph, hyperplane arrangement, finite field method.

(Concerned with sequences \underline{A005840}, \underline{A039757}, and \underline{A341769}.)

Received February 3 2021; revised versions received February 19 2021; February 21 2021. Published in Journal of Integer Sequences, April 26 2021.

Return to Journal of Integer Sequences home page.