BOOLEAN COMPLEXES FOR FERRERS GRAPHS

ANDERS CLAESSON, SERGEY KITAEV, KÁRI RAGNARSSON, AND BRIDGET EILEEN TENNER

Abstract. In this paper we provide an explicit formula for calculating the boolean number of a Ferrers graph. By previous work of the last two authors, this determines the homotopy type of the boolean complex of the graph. Specializing to staircase shapes, we show that the boolean numbers of the associated Ferrers graphs are the Genocchi numbers of the second kind, and obtain a relation between the Legendre-Stirling numbers and the Genocchi numbers of the second kind. In another application, we compute the boolean number of a complete bipartite graph, corresponding to a rectangular Ferrers shape, which is expressed in terms of the Stirling numbers of the second kind. Finally, we analyze the complexity of calculating the boolean number of a Ferrers graph using these results and show that it is a significant improvement over calculating by edge recursion.

1. Introduction

Ferrers shapes, or Young shapes or partitions, are classical combinatorial objects arising in a variety of contexts including Schubert varieties, symmetric functions, hypergeometric series, permutation statistics, quantum mechanical operators, and inverse rook problems (see references in [2]). To such an object, one can relate a bipartite graph known as a Ferrers graph, as introduced in [5].

Let λ = (λ_{1}, …, λ_{r}) be a partition, where λ_{1} ≥ ⋯ ≥ λ_{r} ≥ 0. The associated bipartite Ferrers graph has vertices {x_{1}, …, x_{r}} ⊔ {y_{1}, …, y_{λ_{1}}}, and edges {{x_{i}, y_{j}} : x_{i} ≥ j}. In particular, vertex x_{i} has degree λ_{i}. A Ferrers graph and its associated Ferrers shape are depicted in Figure 1. Note that if λ_{i} = 0 then x_{i} is an isolated vertex in this graph.

y^{1} y^{2} y^{3} y^{4} x_{1} x_{2} x_{3}

Figure 1. A Ferrers graph and its associated Ferrers shape λ = (4, 4, 2).

A selection of enumerative properties of Ferrers graphs are studied in [5], where the graphs are introduced. In particular, expressions for the number of spanning trees, the number of Hamiltonian paths, the chromatic polynomial, and the chromatic symmetric function are given.

In [4], the authors find the number of independent sets of a Ferrers graph, and give relations between the set of independent sets of a Ferrers graph and certain combinatorial objects. Moreover, it is shown in [4] that the simplicial complex related to the set of independent sets of a non-rectangular Ferrers graph is simple-homotopic to a point, whereas it is simple-homotopic to two points in the case of a rectangular Ferrers graph.

Monomial and toric ideals associated to Ferrers graphs are studied in [2]. In particular, it is shown that the edge ideal of a Ferrers graph, called the Ferrers ideal, has a 2-linear minimal free resolution. That is, it defines a small subscheme, which is proved to characterize Ferrers graphs among bipartite graphs.

2000 Mathematics Subject Classification. Primary 05A15; Secondary 55P15, 05C99, 05A19.

Key words and phrases. Ferrers graph, Ferrers shape, partition, Legendre-Stirling numbers, Genocchi numbers of the second kind, Stirling number of the second kind, (complete) bipartite graph, homotopy type, boolean complex, boolean number, complexity.

In this paper, we study the homotopy type of the boolean complexes of Ferrers graphs. Roughly speaking, the boolean complex of a graph G is the complex of words on the vertex set of G, without repeated letters, where two letters commute if the corresponding vertices are not connected by an edge in G. Boolean complexes were introduced in [9], where it is shown that the boolean complex of a graph G on n vertices always has the homotopy type of a wedge of spheres of dimension n − 1. The homotopy type is therefore determined by the number of spheres in the wedge sum, which we denote β(G), and refer to as the boolean number of G.

The paper is organized as follows. In Section 2 we recall the definitions and results on Boolean complexes from [9] that will be needed in this paper, as well as more general functions related to the boolean number and some well-known sequences that arise in the course of this article. In Section 3 we provide a recursion for calculating the boolean number of an arbitrary Ferrers graph in terms of certain truncated shapes (Theorem 3.4). This formula is used in Section 4 to derive an identity (Theorem 4.3) for the boolean number in terms of certain recursively defined coefficients c_{λ}(n, j). More precisely, if F is the Ferrers graph associated to a Ferrers shape λ = (λ_{1}, …, λ_{r}), then

β(F) = ∑_{j=0}^{r} c_{λ}(r, j) · j^{λ_{r}}.

We restrict to Ferrers graphs for staircase shapes in Section 5, obtaining a connection to the Legendre-Stirling numbers. This yields an explicit double sum formula for β(F) in this case (Corollary 5.3). Intriguingly, the boolean numbers of staircase shapes are the Genocchi numbers of the second kind. As a corollary, we find a relationship between the Legendre-Stirling numbers {d(r, j)} and the Genocchi numbers of the second kind {g(r)} that seems to be new in the literature:

g(r) = ∑_{j=1}^{r}(−1)^{r+j}(j!)^{2} · d(r, j).

Applying Theorem 3.4 to complete bipartite graphs K_{r,k} in Section 6, we express β(K_{r,k}) in terms of Stirling numbers of the second kind:

β(K_{r,k}) = ∑_{j=1}^{r}(−1)^{r−j}j! \begin{cases}r + 1 \\ j + 1 \end{cases}\} j^{k}.

Finally, in Section 7, we analyze the complexity of computing the boolean number of a Ferrers graph using the result of Theorem 4.3, and we show that this is a significant improvement over calculating the boolean number using the edge-recursion from [9].

2. Background material

2.1. Boolean complexes. The motivating object in this paper is the boolean complex of a graph, as defined in [9]. We now recall the basic definitions relating to boolean complexes, and the main result about their homotopy type (Theorem 2.5). The reader is referred to [9] for a thorough discussion.

Definition 2.1. Let G be a finite simple graph with vertex set V. Construct a simplicial poset 𝔹(G) whose elements are equivalence classes of strings of distinct elements of V, where two strings are equivalent if one can be transformed into the other by commuting elements that are non-adjacent in G. The partial order on 𝔹(G) is induced by substring inclusion. To the poset 𝔹(G) we associate the regular cell complex Δ(G), called the boolean complex of G. The geometric realization of this complex is denoted |Δ(G)|.

As discussed in [9] and reiterated in Theorem 2.5 below, this |Δ(G)| is homotopy equivalent to the wedge of β(G) spheres, and the boolean number β(G) of a graph can be calculated recursively using three edge operations.

Definition 2.2. Let G be a (multi-)graph and e an edge in G.

• Deletion: G − e is the graph obtained by deleting the edge e.

• Contraction: G ↓ e is the graph obtained by contracting the edge e.

• Simple contraction: When G is a simple graph, G/e is the graph obtained from G ↓ e by removing all loops and redundant edges.

• Extraction: G − [e] is the graph obtained by removing the edge e and its incident vertices.

Definition 2.3. For a finite graph G, let |G| denote the number of vertices in G. Also, for n ≥ 1, let δ_{n} be the graph consisting of n disjoint points.

Definition 2.4. For integers b, r ≥ 0, the notation b·S^{r} is used to indicate a wedge sum of b spheres of dimension r. In particular, 0 · S^{r} is a single point.

We can now state the main theorem on the homotopy type of a boolean complex, as well as another useful result of [9]. The symbol ≃ is used in the statement to denote homotopy equivalence.

Theorem 2.5 ([9, Theorem 3.4]). For every finite simple graph G, there is an integer β(G) so that |Δ(G)| ≃ β(G) · S^{|G|−1}. Moreover, the values β(G) can be computed recursively using the equations

β(G) = β(G − e) + β(G/e) + β(G − [e]) if e is an edge in G,
β(δ_{n}) = 0, and
β(∅) = 1.

Proposition 2.6 ([9, Corollary 7.2]). A finite simple graph G satisfies β(G) = 0 if and only if G has an isolated vertex.

2.2. Connections between the boolean number and other functions. The function β is related to several functions that have been studied previously; namely the universal edge elimination polynomial [1], the bivariate chromatic polynomial [3], and the rank generating function. We highlight these connections primarily for the sake of context, but also because they enable the complexity analysis of Section 7. The reader is refered to [1] and [3] for more information about these functions.

The universal edge elimination polynomial ξ was introduced in [1]. It is defined on multi-graphs G and is determined by the recursive definition

ξ(G, x, y, z) = ξ(G − e, x, y, z) + yξ(G ↓ e, x, y, z) + zξ(G − [e], x, y, z),
ξ(G_{1} ⊕ G_{2}, x, y, z) = ξ(G_{1}, x, y, z) · ξ(G_{2}, x, y, z),
ξ(δ_{1}) = x, and
ξ(∅) = 1.

The “universal” property of ξ is that any polynomial defined on multi-graphs that satisfies a linear edge-recurrence relation is an evaluation of ξ. To apply this property to β, which satisfies a linear edge recurrence but is only defined on simple graphs, we use the following lemma, which follows immediately from the recurrence for ξ.

Lemma 2.7. Fix a graph G and an edge e. If more than one edge connects the endpoints of e, then ξ(G, x, −1, z) = ξ(G − e, x, −1, z).

When G is simple, the graphs G − e and G − [e] are simple as well. However, G ↓ e may have multiple edges (although not loops). Using Lemma 2.7 we deduce that, for a simple graph G,

ξ(G, x, −1, z) = ξ(G − e, x, −1, z) − ξ(G/e, x, −1, z) + zξ(G − [e], x, −1, z).

In particular, we obtain the following characterization of β.

Proposition 2.8. If G is a simple graph, then β(G) = (−1)^{|G|}ξ(G, 0, −1, 1).

Proof. The two invariants satisfy the same recursion with the same initial conditions. □

Notice that the graph invariant ξ(G, 0, 1, 1) satisfies the recurrence

ξ(G, 0, 1, 1) = ξ(G − e, 0, 1, 1) + ξ(G ↓ e, 0, 1, 1) + ξ(G − [e], 0, 1, 1).

However it is not true that β(G) = ξ(G, 0, 1, 1), as ξ(G ↓ e, 0, 1, 1) ≠ ξ(G/e, 0, 1, 1) in general.

For a graph G and x, y ≥ 0, the bivariate chromatic polynomial P (G, x, y) counts the number of colorings of G using y proper colors and x − y improper colors. In such a coloring, two vertices colored by the same proper color may not be connected by an edge, but one may have the same improper color on both endpoints of an edge. Using a linear edge recurrence, it is shown in [1] that P (G, x, y) = ξ(G, x, −1, x − y). Proposition 2.8 then implies the following result.

Corollary 2.9. If G is a simple graph, then β(G) = (−1)^{|G|}P (G, 0, −1).

Also, if R_{P} (t) is the rank generating function of a ranked poset P, then one easily obtains

β(G) = (−1)^{|G|} · R_{𝔹(G)}(−1)

by comparing each side of the equation to the Euler characteristic of 𝔹(G).

2.3. Sequences appearing in this paper. The Legendre-Stirling numbers are defined in [6] as

d(i, j) = ∑_{ℓ=1}^{j} \frac{(−1)^{ℓ+j}(2ℓ + 1)(ℓ^{2} + ℓ)^{i}}{(ℓ + j + 1)!(j − ℓ)!} .  (1)

These are sequence A071951 of [10].

The Genocchi numbers of the second kind (also known as the median Genocchi numbers) have several definitions (see [10, A005439] and references therein). One interpretation is that they count permutations a_{1}a_{2} ⋯ a_{2n+1} ∈ S_{2n+1} such that a_{i} > i if i is odd and i < n, and a_{i} ≤ i if i is even.

The well-known Stirling numbers of the second kind count partitions of an n element set into k nonempty blocks. It is sequence A008277 of [10].

3. Recursion for a general Ferrers shape

As mentioned previously, we make the convention that a Ferrers shape has a specified number of rows, even if some of these rows are empty. Such a Ferrers shape corresponds to a partition into a prescribed number of parts, where some parts are allowed to be zero.

Definition 3.1. For a Ferrers shape λ, the Ferrers graph associated to λ is denoted F (λ). When no confusion will arise, the notation β(λ) will be taken to mean β(F (λ)). If the shape λ has r rows and λ_{1} columns, then the vertices of F (λ) will be denoted {x_{1}, …, x_{r}} ⊔ {y_{1}, …, y_{λ_{1}}}, and there is an edge {x_{i}, y_{j}} if and only if λ_{i} ≥ j.

If λ has a row of length zero, that is, if some λ_{i} equals 0, then the corresponding vertex x_{i} has no incident edges. Consequently, the boolean number of such a graph is 0, by Proposition 2.6.

The aim of this section is to obtain a recursive formula for the boolean number of a Ferrers shape, based on the length of its bottom row. First we define the shapes appearing in the recursion.

Definition 3.2. For a Ferrers shape λ = (λ_{1}, …, λ_{r}) with r > 1 rows, set \underline{λ} to be the shape (λ_{1}, …, λ_{r−1}), obtained by deleting the bottom row from λ.

Definition 3.3. For a Ferrers shape λ = (λ_{1}, …, λ_{r}), and an integer t ≥ −λ_{r}, define the shape

λ[t] = (λ_{1} + t, λ_{2} + t, …, λ_{r} + t).

The shape λ[t] is obtained from λ by appending t columns of length r to the left side of the shape λ. If t < 0, then these columns are actually deleted from λ. When t = −λ_{r}, this means that all the boxes in the bottom row of λ are deleted, so the bottom row of λ[−λ_{r}] is empty. Furthermore, for all i such that λ_{i} = λ_{r}, the i-th row of the shape λ[−λ_{r}] is empty.

Theorem 3.4. The boolean number of the Ferrers graph associated to the shape λ = (λ_{1}, …, λ_{r}), can be computed recursively according to the formula

β(λ) = \begin{cases}1 & if r = 1; \\ λ_{r} · β(\underline{λ}) + ∑_{ℓ=1}^{λ_{r}} \binom{λ_{r}+1}{ℓ+1} · β(\underline{λ}[−ℓ]) & if r > 1. \end{cases}  (2)

Proof. If r = 1, then the graph is a star, and the boolean number of this graph is 1 (see [9]). The remainder of the theorem is proved by induction on λ_{r}.

Assume that r > 1. Let the vertex x_{r} ∈ F (λ) correspond to the last (r-th) row of λ. Thus the degree of x_{r} is λ_{r}. We apply the edge-recursion of Theorem 2.5 at the edge {x_{r}, y_{λ_{r}}}, which corresponds to the rightmost box of the bottom row in λ. The recursion involves three operations: deletion, extraction, and simple contraction. The first two of these operations translate easily into the language of Ferrers graphs. More precisely, deleting {x_{r}, y_{λ_{r}}} corresponds to deleting the λ_{r}-th box from the r-th row of λ, which means subtracting 1 from the last part of the partition λ. Note that we still require that this shape have r rows, although the bottom row will be empty if λ_{r} = 1. Likewise, extracting {x_{r}, y_{λ_{r}}} corresponds to deleting the entire r-th row and λ_{r}-th column from λ, which gives the shape \underline{λ}[−1].

Thus it remains to understand what happens when {x_{r}, y_{λ_{r}}} is contracted. Unfortunately, if λ_{r} > 1, the resulting graph is no longer bipartite, and so does not correspond to a Ferrers shape. However, if λ_{r} = 1, then contracting \{x_{r}, y_{1}\} yields the graph \underline{λ}. In this case, when λ_{r} = 1, the graph obtained after deleting {x_{r}, y_{1}} has an isolated vertex, which has boolean number 0. Thus, if λ_{r} = 1, then β(λ) equals β(\underline{λ}) + β(\underline{λ}[−1]), which proves equation (2) in the base case.

Now suppose that the result has been proved when the last row of the shape has length less than λ_{r}. Then deleting the edge {x_{r}, y_{λ_{r}}} contributes

β((λ_{1}, …, λ_{r−1}, λ_{r} − 1)) = (λ_{r} − 1) · β(\underline{λ}) + ∑_{ℓ=2}^{λ_{r}} \binom{λ_{r}}{ℓ} · β(\underline{λ}[−(ℓ − 1)]),

to β(λ), while extracting \{x_{r}, y_{λ_{r}}\} contributes β(\underline{λ}[−1]). Combining these values gives the sum

(λ_{r} − 1) · β(\underline{λ}) + (\binom{λ_{r}}{2} + 1) · β(\underline{λ}[−1]) + ∑_{ℓ=3}^{λ_{r}} \binom{λ_{r}}{ℓ} · β(\underline{λ}[−(ℓ − 1)]).  (3)

For a Ferrers shape μ, let F′(μ) be the (likely non-bipartite) graph obtained from F (μ) by contracting the edge corresponding to the rightmost box in the bottom row of μ. With F′(λ) defined in this way, the boolean number β(λ) is equal to the sum of β(F′(λ)) and the expression in (3). We prove by induction on λ_{r} ≥ 2 that β(F′(λ)) equals

β(\underline{λ}) + (λ_{r} − 1) · β(\underline{λ}[−1]) + ∑_{ℓ=2}^{λ_{r}} \binom{λ_{r}}{ℓ} · β(\underline{λ}[−ℓ]).  (4)

This is straightforward to show if λ_{r} = 2, because the first term corresponds to deleting the edge between y_{1} and y_{2} in F′(λ), the second term corresponds to contracting this edge, and the last term represents extracting the edge. Now suppose inductively that the equality holds for all shapes whose last rows have fewer than λ_{r} boxes.

Deleting the edge {y_{1}, y_{λ_{r}}} from the graph F′(λ) yields the graph

F′((λ_{1}, …, λ_{r−1}, λ_{r} − 1)).

Likewise, extracting the edge \{y_{1}, y_{λ_{r}}\} gives the graph F (\underline{λ}[−2]). Finally, contracting the edge {y_{1}, y_{λ_{r}}} yields the graph F′(λ[−1]). Hence

β(F′(λ)) = β(F′((λ_{1}, …, λ_{r−1}, λ_{r} − 1))) + β(\underline{λ}[−2]) + β(F′(λ[−1])),

and β(F′(λ)) equals the expression in (4) by the inductive hypothesis and a binomial identity. Finally, we combine the expressions in (3) and (4) to complete the proof. □

4. Formula for general Ferrers shape

In this section we obtain an explicit formula for the boolean number of a Ferrers graph.

Definition 4.1. For a Ferrers shape λ = (λ_{1}, …, λ_{r}) with r rows, define the numbers c_{λ}(i, j), where 1 ≤ i ≤ r and j ∈ ℤ, recursively by

c_{λ}(1, j) = \begin{cases}−1 & if j = 0, \\ 1 & if j = 1, \\ 0 & if j ∉ \{0, 1\}, \end{cases}

and, for 1 < i ≤ r,

c_{λ}(i, j) = j(j − 1)^{(λ_{i−1}−λ_{i})} · c_{λ}(i − 1, j − 1) − (j + 1)j^{(λ_{i−1}−λ_{i})} · c_{λ}(i − 1, j).

Here we use the convention 0^{0} = 1. Note that it follows directly from the definition that c_{λ}(i, j) only takes nonzero values when 0 ≤ j ≤ i, and so the values c_{λ}(i, j) can be calculated by means of a triangle. The zero values c_{λ}(i, j) for j < 0 or j > i play no role in the paper, but are included in the definition so that we avoid exceptions in the recursive definition.

As an example, the triangle used to calculate c_{λ}(i, j) for the Ferrers shape λ = (7, 7, 7, 6, 4, 4, 2) is given in Table 1. This triangle exhibits three interesting phenomena, each of which can be shown to hold for any Ferrers shape. First the entries in the leftmost column are zero after the third row. (In general one has c_{λ}(i, 0) = 0 when λ_{i} < λ_{1}.) Second, when one disregards the leftmost columns, adjacent entries in the triangle have alternating signs. Third, the entries in each row sum to zero.

i j = 0  1  2  3  4  5  6  7
1  −1  1
2  1 −3  2
3  −1  7  −12  6
4  0 −14  86  −144  72
5  0 28 −1060  6216  −10944  5760
6  0 −56  3236 −28044  79584 −89280  34560
7  0 112 −38944 1048416 −7376304 19758720 −22101120 8709120

Table 1. The triangle calculating c_{λ}(i, j) for λ = (7, 7, 7, 6, 4, 4, 2).

Lemma 4.2. Let λ = (λ_{1}, …, λ_{r}) be a Ferrers shape with r rows.

(a) c\underline{λ}(i, j) = c_{λ}(i, j), for all integers i and j with 1 ≤ i ≤ r − 1.

(b) If t ≥ −λ_{r}, then c_{λ[t]}(i, j) = c_{λ}(i, j) for all integers i and j with 1 ≤ i ≤ r.

Proof. From the recursive definition of the numbers c_{λ}(i, j), we see that they depend only on the differences λ_{ℓ−1} − λ_{ℓ}. Forming \underline{λ} does not change these differences for ℓ ≤ r − 1, proving part (a). Similarly, forming λ[t] from λ does not change any differences, proving part (b). □

Theorem 4.3. The boolean number of the Ferrers graph associated to the shape λ = (λ_{1}, …, λ_{r}) is

β(λ) = ∑_{j=0}^{r} c_{λ}(r, j) · j^{λ_{r}}.

Proof. We prove this by induction on r using the recursive formula in Theorem 3.4. The base case, where r = 1, is easily checked.

To save notation we write c(i, j) instead of c_{λ}(i, j). This should not cause any confusion since, for 1 ≤ i ≤ r − 1 and ℓ ≤ λ_{r}, Lemma 4.2 yields c_{λ}(i, j) = c\underline{λ}(i, j) = c_{\underline{λ}[−ℓ]}(i, j).

Assuming that the result is true for shapes with at most r−1 rows, we have the following sequence of equalities, where the first equality follows from equation (2):

β(λ) = λ_{r} · β(\underline{λ}) + ∑_{ℓ=1}^{λ_{r}} \binom{λ_{r} + 1}{ℓ + 1} · β(\underline{λ}[−ℓ])

= λ_{r} ∑_{j=0}^{r−1} c(r − 1, j) · j^{λ_{r−1}} + ∑_{ℓ=1}^{λ_{r}} (\binom{λ_{r} + 1}{ℓ + 1} · ∑_{j=0}^{r−1} c(r − 1, j) · j^{λ_{r−1}−ℓ})

= ∑_{j=0}^{r−1} c(r − 1, j) ((∑_{ℓ=0}^{λ_{r}} \binom{λ_{r} + 1}{ℓ + 1}j^{λ_{r−1}−ℓ}) − j^{λ_{r−1}})

= ∑_{j=0}^{r−1} c(r − 1, j) · ((j^{λ_{r−1}−λ_{r}} ((j + 1)^{λ_{r}+1} − j^{λ_{r}+1})) − j^{λ_{r−1}})

= ∑_{j=0}^{r−1} c(r − 1, j) · (j^{λ_{r−1}−λ_{r}}(j + 1) ((j + 1)^{λ_{r}} − j^{λ_{r}})) .  (5)

If we recall that c(r − 1, −1) = c(r − 1, r) = 0, then rewriting the sum and collecting terms yields

∑_{j=0}^{r} ((j − 1)^{λ_{r−1}−λ_{r}}j · c(r − 1, j − 1) − j^{λ_{r−1}−λ_{r}}(j + 1) · c(r − 1, j)) · j^{λ_{r}}

on the right hand side of (5), and as the coefficient of j^{λ_{r}} equals c(r, j), this completes the proof. □

5. Staircase shapes

Definition 5.1. For r ≥ 1, a staircase shape of height r is the Ferrers shape σ_{r} = (r, r − 1, …, 2, 1).

For a staircase shape σ_{r}, the recursive formula for c_{σ_{r}}(i, j) simplifies to

c_{σ_{r}}(i, j) = j(j − 1) · c_{σ_{r}}(i − 1, j − 1) − (j + 1)j · c_{σ_{r}}(i − 1, j).

Note, in particular, that c_{σ_{r}}(i, 0) = 0 for i > 1.

i j = 0  1  2  3  4  5  6  7
1  −1  1
2  0 −2  2
3  0  4  −16  12
4  0 −8  104  −240  144
5  0 16  −640  3504  −5760  2880
6  0 −32  3872 −45888  157248 −201600  86400
7  0 64 −23296 573888 −3695616 9192960 −9676800 3628800

Table 2. The triangle calculating c_{σ(7)}(i, j).

Corollary 5.2. For r ≥ 1, the values

\{\frac{(−1)^{r+j}}{j!(j − 1)!} · c_{σ_{r}}(r, j)\}  (6)

are the Legendre-Stirling numbers. Proof. The sequence in (6) has the same initial values and the same recurrence as the Legendre-Stirling numbers, given in [10, A071951]. □

The Legendre-Stirling numbers are discussed in [6] and [8]. From the formula for the Legendre-Stirling numbers (equation (1)), one obtains a formula for c_{σ_{r}}(r, j), and thus for β(σ_{r}) as well.

Corollary 5.3. For r ≥ 1,

β(σ_{r}) = ∑_{j=1}^{r} ∑_{ℓ=1}^{j}(−1)^{r+ℓ} \frac{(2ℓ + 1)(ℓ^{2} + ℓ)^{r} · j!j!}{(ℓ + j + 1)!(j − ℓ)!}.

In fact, the boolean numbers of staircase shapes form a known sequence.

Corollary 5.4. The values {β(σ_{r})}_{r≥1} are the sequence of Genocchi numbers of the second kind.

Proof. The Genocchi numbers of the second kind {g(r)} can be calculated by g(r) = G(r, 1), where G(r, x) is the function defined recursively by

G(r, x) = (x + 1)^{2}G(r − 1, x + 1) − x(x + 1)G(r − 1, x) and
G(1, x) = 1

for all x ≥ 0 and r ≥ 2.

By a simple induction on i, for 1 ≤ i ≤ r, one can prove that G(r, 1) equals

∑_{j=1}^{i} j · c_{σ_{r}}(i, j) · G(r + 1 − i, j).

The base case i = 1 is trivial, and the inductive step follows easily from the recursive formulas for G(r, x) and c_{σ_{r}}(i, j). When i = r, we have G(r + 1 − i, j) = 1, and the equation simplifies to

g(r) = G(r, 1) = ∑_{j=1}^{i} j · c_{σ_{r}}(r, j) = β(σ_{r}).

□

Corollaries 5.2 and 5.4 reveal a relationship between the Legendre-Stirling numbers {d(r, j)} and the Genocchi numbers of the second kind {g(r)} that seems to be new in the literature.

Corollary 5.5. The Genocchi numbers of the second kind {g(r)} and the Legendre-Stirling numbers {d(r, j)} are related by the equation

g(r) = ∑_{j=1}^{r}(−1)^{r+j}(j!)^{2} · d(r, j).

Corollary 5.2 says in particular that, for a fixed j ≥ 1, the sequence

\{\frac{(−1)^{i+j}}{j!(j − 1)!} · c_{σ_{r}}(i, j)\}_{i≥1}

has the same generating function as the Legendre-Stirling numbers, namely

\frac{x^{j}}{∏_{ℓ=1}^{j} (1 − ℓ(ℓ + 1)x)}.

This result can be generalized to staircases of other steplengths as follows.

Definition 5.6. For r, d ≥ 1, a staircase shape of height r with steplength d is the Ferrers shape σ_{r,d} = (rd, (r − 1)d, …, 2d, d).

Proposition 5.7. Let σ_{r,d} be a staircase shape of height r and steplength d, and put

ĉ_{σ_{r,d}}(i, j) = \frac{(−1)^{i+j}c_{σ_{r,d}}(i, j)}{j! ((j − 1)!)^{d}}.

For j ≥ 1, the sequence {ĉ_{σ_{r,d}}(i, j)}_{i≥1} has generating function

F_{j}(x) = \frac{x^{j}}{∏_{i=1}^{j} (1 − i^{d}(i + 1)x)}.

Proof. The recursive formula for c_{σ_{r,d}}(i, j) is

c_{σ_{r,d}}(i, j) = j(j − 1)^{d} · c_{σ_{r,d}}(i − 1, j − 1) − (j + 1)j^{d} · c_{σ_{r,d}}(i − 1, j).  (7)

Multiplying equation (7) by \frac{(−1)^{i+j}}{j!((j−1)!)^{d}} yields

ĉ_{σ_{r,d}}(i, j) = ĉ_{σ_{r,d}}(i − 1, j − 1) + (j + 1)j^{d}ĉ_{σ_{r,d}}(i − 1, j).  (8)

Let the generating function for the sequence {ĉ_{σ_{r,d}}(i, j)}_{i≥1} be F_{j}(x) = ∑_{i≥1} ĉ_{σ_{r,d}}(i, j)x^{i}. Then equation (8) gives F_{j}(x) = xF_{j−1}(x) + (j + 1)j^{d}xF_{j}(x), which shows that

F_{j}(x) = \frac{x^{j}}{∏_{i=1}^{j} (1 − i^{d}(i + 1)x)}.

□

6. Complete bipartite graphs

In this section we consider the r row shape λ = (k, …, k). In other words, λ is a rectangle having r rows and k columns. The corresponding Ferrers graph is the complete bipartite graph K_{r,k}. For a rectangular shape, the recursive formula for c_{λ}(i, j) simplifies to

c_{λ}(i, j) = j · c_{λ}(i − 1, j − 1) − (j + 1) · c_{λ}(i − 1, j).

Proposition 6.1. For positive integers r and k, we have

β(K_{r,k}) = ∑_{j=1}^{r}(−1)^{r−j}j!\left\{{r + 1 \atop j + 1}\right\}j^{k},

where \left\{{r+1 \atop j+1}\right\} denotes a Stirling number of the second kind.

Proof. Let a(i, j) = (−1)^{i−j}j!\left\{{i+1 \atop j+1}\right\}. Trivially, a(1, j) = c_{λ}(1, j). From the familiar recursion \left\{{i+1 \atop j+1}\right\} = \left\{{i \atop j}\right\} + (j + 1) · \left\{{i \atop j+1}\right\} for the Stirling numbers it follows that

a(i, j) = j · a(i − 1, j − 1) − (j + 1) · a(i − 1, j).

Thus a(i, j) and c_{λ}(i, j) satisfy the same recursion. □

Note that this result can also be obtained as a consequence of [3, Section 5.2], where a similar result is proved for the bivariate chromatic polynomial.

7. Computational complexity

We conclude by addressing the computational complexity (that is, the cost) of calculating β(λ) by means of a triangle, as in Theorem 4.3, in order to illustrate the advantage of this method over calculating by edge recursion. More precisely, we show that, while calculating boolean numbers by edge recursion is #P -hard, calculating the boolean number of a Ferrers shape with n cells using the results from Section 4 requires n^{2}/4 + O(n) multiplications.

The following algorithm calculates the vector (c_{λ}(r, j))_{j=0}^{r}.

1 def Γ(λ_{1}, …, λ_{r}) : 2 if r = 1 : 3 return (−1, 1)

4  else :

5 (c_{−1}, c_{r}) := (0, 0) 6 (c_{0}, …, c_{r−1}) := Γ(λ_{1}, …, λ_{r−1}) 7 d_{r}:= λ_{r−1} − λ_{r} 8 return ( j(j − 1)^{d_{r}}c_{j−1} − (j + 1)j^{d_{r}}c_{j} | j = 0, …, r )

We shall analyze the dominant factor in the running time of Γ, the number of multiplications that it uses; let f(λ) be that number. The multiplications are carried out in row 6 (the recursive call) and row 8. To be precise, for r > 1 we have

f(λ_{1}, …, λ_{r}) = f(λ_{1}, …, λ_{r−1}) + 2(r + 1)(d_{r} + 1),

and for r = 1 we have f((λ_{1})) = 0. Solving this simple recursion we get

f(λ_{1}, …, λ_{r}) = 2 ∑_{i=2}^{r}(i + 1)(d_{i} + 1) = 2 ∑_{i=2}^{r} id_{i} + 2 ∑_{i=2}^{r} d_{i} + 2 ∑_{i=2}^{r}(i + 1)

= 2 ∑_{i=2}^{r} id_{i} + 2(λ_{1} − λ_{r}) + r^{2} + O(r).

Because d_{i} = λ_{i−1} − λ_{i}, we have

∑_{i=2}^{r} id_{i} = ∑_{i=2}^{r} iλ_{i−1} − ∑_{i=2}^{r}(i + 1)λ_{i} + ∑_{i=2}^{r} λ_{i} = 2λ_{1} − (r + 1)λ_{r} + n − λ_{1} = λ_{1} − (r + 1)λ_{r} + n,

where n = λ_{1} + ⋯ + λ_{r} is the total number of cells. Thus

f(λ_{1}, …, λ_{r}) = 2(λ_{1} − (r + 1)λ_{r} + n) + 2(λ_{1} − λ_{r}) + r^{2} + O(r)
= 2n + r^{2} + O(rλ_{r} + λ_{1}).

The graphs for λ and for its transpose λ′ have the same boolean number, so we can assume that r ≤ λ_{1}. Then r + λ_{1} − 1 ≤ n, and thus r ≤ (n + 1)/2. Also, rλ_{r} + λ_{1} < 2n. Thus,

f(λ) = 2n + (n + 1)^{2}/4 + O(n) = n^{2}/4 + O(n).

Corollary 7.1. The number of multiplications needed to calculate β(λ) using Theorem 4.3 is

n^{2}/4 + O(n),

where n is the total number of cells of λ.

By comparison, calculating the boolean number using edge recursion is, in general, #P -hard. This follows from the relationship to the bivariate chromatic polynomial, β(G) = P (G, 0, −1), and from a result in [7] saying that computing P (G, x, y) is #P -hard, unless y = 0 or (x, y) ∈ {(1, 1), (2, 2)}.

Remark 7.2. The coefficients c_{λ}(i, j) in the triangle for computing β(λ) grow exponentially in i and polynomially in j, and the size of these numbers affects the cost of the algorithm. We obtain an upper bound for the running time, taking the size of the coefficients into account by making the following observations. First, the cost of multiplying two numbers is bounded by the product of their binary logarithms. Next, all the multiplications in the algorithm are of the form (j + 1)j^{d_{r}}c_{j}. We can make the bounds log(j) < log(j + 1) ≤ log(n). Also, going through the algorithm, the order of the size of log(c_{j}) can be bounded by O(n log(n)). Thus the cost of each multiplication is bounded by O(n log(n)), and the total cost of the algorithm, accounting for the size of the coefficients, is bounded by O(n^{3} log(n)^{2}).

References

[1] I. Averbouch, B. Godlin, and J. A. Makowski, An extension of the bivariate chromatic polynomial, preprint.

[2] A. Corso and U. Nagel, Monomial and toric ideals associated to Ferrers graphs, Trans. Amer. Math. Soc., 361 (2009), 1371–1395.

[3] K. Dohmen, A. Pönitz, and P. Tittmann, A new two-variable generalization of the chromatic polynomial, Discrete Math. Theor. Comput. Sci., 6 (2003), 69–90.

[4] R. Ehrenborg and S. Kitaev, Ferrers graphs, their independent sets and independence complexes, in preparation.

[5] R. Ehrenborg and S. van Willigenburg, Enumerative properties of Ferrers graphs, Discrete Comput. Geom. special issue in honor of Louis J. Billera, 32 (2004), 481–492.

[6] W. N. Everitt, L. L. Littlejohn and R. Wellman, Legendre polynomials, Legendre-Stirling numbers, and the leftdefinite spectral analysis of the Legendre differential expression, J. Comput. Appl. Math. 148 (2002), 213–238.

[7] C. Hoffmann, A most general edge elimination polynomial – thickening of edges, arXiv:0801.1600.

[8] L. L. Littlejohn and R. Wellman, A general left-definite theory for certain self-adjoint operators with applications to differential equations, J. Differential Equations, 181 (2002), 280–339.

[9] K. Ragnarsson and B. E. Tenner, Homotopy type of the boolean complex of a Coxeter system, arXiv:0806.0906.

[10] N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at

   http://www.research.att.com/~njas/sequences/.

The Mathematics Institute, Reykjavík University, Iceland

  E-mail address: anders@ru.is, sergey@ru.is, kariragnars@ru.is

Department of Mathematical Sciences, DePaul University, Chicago, Illinois

  E-mail address: bridget@math.depaul.edu