# On the monotone hook hafnian conjecture

Mirkó Visontai¹

¹Department of Mathematics, University of Pennsylvania, Philadelphia, PA, USA

**Abstract.** We investigate a conjecture of Haglund that asserts that certain graph polynomials have only real roots. We prove a multivariate generalization of this conjecture for the special case of threshold graphs.

**Résumé.** Nous étudions une conjecture de Haglund qui affirme que certaines polynômes des graphes ont uniquement des racines réelles. Nous prouvons une généralisation multivariée de cette conjecture pour le cas particulier des graphes à seuil.

**Keywords:** hafnian, threshold graphs, monotone hook, only real roots, stable polynomial

## 1 Introduction

Caianiello (1973) defined the hafnian for (upper) triangular arrays as the “signless” pfaffian. There are slight variations in the literature on how to extend the original definition to matrices; we will use the following one. Let $C = (c_{ij})$ be a $2n \times 2n$ symmetric matrix, the hafnian of $C$ is defined as

$$ \operatorname{haf}(C) = \frac{1}{n!2^n} \sum_{\sigma \in \mathfrak{S}_{2n}} \prod_{k=1}^{n} c_{\sigma(2k-1), \sigma(2k)}, \qquad (1) $$

where $\mathfrak{S}_{2n}$ denotes the symmetric group on $2n$ elements.

The $m$th hook of a triangular array (or shifted Ferrers board) $A = (a_{ij})_{1 \le i < j \le n}$ is the set of cells

$$ \operatorname{hook}_m = \{(i, m) \mid i = 1, \dots, m-1\} \cup \{(m, j) \mid j = m+1, \dots, n\}. \qquad (2) $$

The direction along the $m$th hook is the one in which the quantity $i+j$ is increasing where $(i, j) \in \operatorname{hook}_m$. A monotone hook triangular array has real entries decreasing along at least $n-1$ of its hooks, or possibly along all $n$ of them. Analogously, a monotone hook matrix is a real symmetric matrix whose entries above the diagonal form a monotone hook triangular array.

In this paper we discuss results on the following conjecture of Haglund (2000):

**Conjecture 1.1 (Monotone Hook Hafnian (MHH))** Let $A$ be a $2n \times 2n$ monotone hook matrix. Let $J_{2n}$ denote the $2n \times 2n$ matrix of all ones. Then the polynomial $\operatorname{haf}(zJ_{2n} + A) \in \mathbb{R}[z]$ has only real roots.

In Haglund (2000) the MHH conjecture was proven for adjacency matrices of a class of graphs called threshold graphs, and as a corollary for all monotone hook $\{0, 1\}$ matrices. And it was also verified for all $2n \times 2n$ monotone hook matrices for $n \le 2$.
The main result of this paper is a (multivariate) generalization of the MHH conjecture for the special case of adjacency matrices of threshold graphs. We begin by discussing a closely related problem involving permanents and monotone column matrices. In Section 2, we introduce the machinery needed for our proofs from the theory of stable polynomials. In Section 3, we prove the multivariate generalization of the MHH conjecture for the special case of threshold graphs. We also mention some negative results and some open problems. We conclude in Section 4 by giving an alternative proof of the MHH conjecture for some threshold graphs whose adjacency matrices can be written in a special form.

## 1.1 A closely related problem: the MCP theorem

Recall the definition of the permanent of an $n \times n$ matrix $B$ with entries $b_{ij}$:

$$ \mathrm{per}(B) = \sum_{\sigma \in \Sigma_n} \prod_{i=1}^{n} b_{i, \sigma(i)}. \qquad (3) $$

A monotone column matrix $A \in \mathbb{R}^{n \times n}$ has real entries $a_{ij}$ weakly decreasing down columns: $a_{ij} \ge a_{i+1,j}$ for all $1 \le i < n$ and $1 \le j \le n$. Building on recent developments in the theory of stable polynomials by Borcea and Brändén (see, for instance, Borcea and Brändén (2010) or Wagner (2011) for a survey) the following theorem was proved in Brändén et al. (2010):

**Theorem 1.2 (Monotone Column Permanent (MCP))** Let $A$ be an $n \times n$ monotone column matrix, and $J_n$ the $n \times n$ matrix of all ones. Then the polynomial $\mathrm{per}(zJ_n + A) \in \mathbb{R}[z]$ has only real roots.

As pointed out in Haglund (2000) the MHH conjecture can be viewed as the analog of the MCP theorem from the complete bipartite graph, $K_{n,n}$ to the complete graph, $K_{2n}$, in the following sense. Given an (undirected) weighted graph $G$ with edge weights $w_{ij}$ define the following graph polynomial

$$ \phi(G; z) = \sum_{\mathcal{M}} \prod_{ij \in \mathcal{M}} (w_{ij} + z), \qquad (4) $$

where $\mathcal{M}$ runs over all perfect matchings of $G$. If $A_G = \begin{pmatrix} 0 & B_G \\ B_G^\top & 0 \end{pmatrix}$ is the adjacency matrix of a weighted $K_{n,n}$ graph $G$, then $\phi(G; z) = \mathrm{per}(zJ_n + B_G)$. Similarly, if $A_H$ is the adjacency matrix of a weighted $K_{2n}$ graph $H$, then $\phi(H; z) = \mathrm{haf}(zJ_{2n} + A_H)$.

Another interesting connection comes from the following basic fact. The hafnian of a matrix does not depend on the diagonal entries of the matrix. Let $A^*$ be a monotone hook matrix that is monotone along all of its hooks. In this case, for the purpose of studying $\mathrm{haf}(A^*)$ we can assume that $A^*$ is a symmetric monotone column matrix (by picking the diagonal entries accordingly). Since $A^*$ is symmetric this will imply that $A^*$ is monotone both down columns and down rows.

In the next section, we describe the results from the theory of stable polynomials that we need for our proof. These results were successfully employed in the proof of the MCP theorem and they turn out to be useful for the MHH conjecture, as well.

# 2 Stable polynomials and stability preservers

A multivariate polynomial $f \in \mathbb{R}[z_1, \dots, z_n]$ is stable if it does not vanish when the imaginary parts of the $z_i$'s are positive. This notion of stability — sometimes referred to as the upper half-plane property
(Fisk (2008)) — has been the focus of some recent research (Brändén (2007); Borcea and Brändén (2009, 2010)). If $f \in \mathbb{R}[z_1, \dots, z_n]$ does not vanish when the real parts of $z_i$'s are positive then we call it *Hurwitz-stable* (Brändén (2007)), sometimes called right half-plane stable.

The technique we use to show that a (univariate) polynomial $f \in \mathbb{R}[z]$ has real roots only is to show that $f$ is stable, since the two notions coincide in $\mathbb{R}[z]$. We show stability of $f$ by finding a stable multivariate generalization of it, namely a suitable stable polynomial $g(z_1, \dots, z_n) \in \mathbb{R}[z_1, \dots, z_n]$ that can be reduced to $f(z)$ using certain operations that preserve stability. Operations that preserve stability play a crucial role in this framework, since they allow for manipulation of multivariate polynomials while maintaining their stability. The following lemma gives a list of such operations that we will be using throughout the paper. The results are taken from Brändén (2007); Borcea and Brändén (2009); Wagner (2011).

**Lemma 2.1** *The following operations preserve stability of polynomials in $\mathbb{R}[z_1, \dots, z_n]$*

1. *Permutation:* for any permutation $\sigma \in \mathfrak{S}_n$, $f \mapsto f(z_{\sigma(1)}, \dots, z_{\sigma(n)})$.

2. *Diagonalization:* for $1 \le i < j \le n$, $f \mapsto f(z_1, \dots, z_n)|_{z_i=z_j}$.

3. *Specialization:* for a with $\mathfrak{S}(a) > 0$, $f \mapsto f(a, z_2, \dots, z_n)$.

4. *Translation:* $f \mapsto f(z_1 + t, z_2, \dots, z_n) \in \mathbb{R}[z_1, \dots, z_n, t]$.

5. *Differentiation:* $f \mapsto \partial f / \partial z_1$.

**3 Multivariate MHH for threshold graphs**

In this section we prove a multivariate generalization of the following theorem of Haglund (see Theorem 2.2 of Haglund (2000)).

**Theorem 3.1 (MHH for threshold graphs)** Let $A_G$ denote the adjacency matrix of a (non-weighted) threshold graph $G$ on $2n$ vertices. Then $\text{haf}(zJ_{2n} + A_G)$ is stable.

Threshold graphs have been widely studied and are known to have several equivalent definitions. For our purposes, the following definition will come in handy (see Theorem 1.2.4 in Mahadev and Peled (1995)). A graph $G$ on $n$ vertices is a *threshold graph* if it that can be constructed starting from a one-vertex graph by adding vertices one at a time in the following way. Start at step 1 with a single vertex $v_1$. At each step $i$, for $2 \le i \le n$, the vertex $v_i$ being added is either isolated (has degree 0) or dominating (has degree $i-1$ at the time when added).

By definition, $\text{haf}(zJ_{2n} + A_G)$ is invariant under the permutation of the vertices in $G$. Hence, we can assume that the vertices of a threshold graph are labeled in the order of the above construction. This means that in any column $i$ for $2 \le i \le 2n$ the entries above the diagonal entry of $zJ_{2n} + A_G$ are equal to either $z$ (if $v_i$ was added as isolated vertex) or $z+1$ (if $v_i$ was added as dominating vertex). This suggests the multivariate generalization that we show next. The idea essentially is to use a separate variable $z_i$ for the entries above the diagonal in each column $i$ (see explicit construction of $A_{2n}(z)$ in Proposition 3.2 below).
## 3.1 A multivariate generalization for hafnians

The following proposition is a direct application of the idea of the proof of Theorem 3.4 of Brändén et al. (2010) to hafnians.

**Proposition 3.2** Let $z_1, \dots, z_{2n}$ denote commuting indeterminates and let $A_{2n}(\mathbf{z}) = (a_{ij})$ denote the $2n \times 2n$ symmetric matrix with entries $a_{ij} = z_{\max(i,j)}$. Then $\text{haf}(A_{2n}(\mathbf{z}))$ is a stable polynomial in $\mathbb{R}[z_2, \dots, z_{2n}]$ ($z_1$ only appears on the diagonal).

**Proof:** We use induction. Clearly, $\text{haf}\left(\begin{pmatrix} z_1 & z_2 \\ z_2 & z_2 \end{pmatrix}\right) = z_2$ is stable, which settles the base case. Next we show that for $n \ge 2$, $\text{haf}(A_{2n})$ is stable if $\text{haf}(A_{2n-2})$ is stable. This follows from the differential recursion:

$$A_{2n}(\mathbf{z}) = z_{2n}A_{2n-2}(\mathbf{z}) + 2z_{2n-1}z_{2n} \sum_{i=2}^{2n-2} \frac{\partial A_{2n-2}(\mathbf{z})}{\partial z_i} \quad (5)$$

This recursion can be seen from the expansion of the hafnian along the last column. The differential operator in the right-hand side preserves stability (analogously to the one in Theorem 3.4 of Brändén et al. (2010)). □

The proposition gives a multivariate version of the MHH conjecture for certain matrices. Unfortunately, it is not clear how to transition from here to the general MHH conjecture. Nevertheless, Proposition 3.2 does imply Theorem 3.1 in the following way.

**Proof of Theorem 3.1:** Let $G$ be a threshold graph on $2n$ vertices with an adjacency matrix $A_G$. Assume that the vertices of $G$ are ordered as in the definition of the vertex-by-vertex construction above. It is easy to see that $A_{2n}(\mathbf{z})$ in Proposition 3.2 specializes to $zJ_{2n} + A_G$ if, for all $i$, we set

$$z_i = \begin{cases} z, & \text{if } v_i \text{ was added as an isolated vertex,} \\ z+1, & \text{if } v_i \text{ was added as a dominating vertex.} \end{cases} \quad (6)$$

This last operation consists of diagonalizing, translating and specializing the variables and thus preserves stability of $\text{haf}(A_{2n}(\mathbf{z}))$ by Lemma 2.1. Hence, we obtain that $\text{haf}(zJ_{2n} + A_G)$ is a stable polynomial. To complete the proof, note that a stable univariate polynomial with real coefficients has only real roots. □

<figure><img src="image_1.png" /></figure>

**Remark 3.3** The same proof goes through if we allow edges to have weights other than zero or one with the additional restriction that when we add a dominating vertex, all edges incident to it must have the same weight (but this weight need not be 1 as before).

## 3.2 Negative results and open problems

In Brändén et al. (2010) a more general, multivariate version of the MCP theorem was also obtained:

**Theorem 3.4 (Multivariate MCP)** Let $A$ be a monotone column matrix, and let $Z_n = \text{diag}(z_1, \dots, z_n)$ be the $n \times n$ diagonal matrix of $n$ indeterminates. Then $\text{per}(J_n Z_n + A) \in \mathbb{R}[z_1, \dots, z_n]$ is stable.

Similarly to the multivariate MCP theorem, we would like to have a multivariate analog of the MHH conjecture that would imply the univariate case. We consider the following three multivariate generalizations. For a monotone hook matrix $A = (a_{ij})$ of size $2n \times 2n$, the diagonal matrix $Z_{2n}$ of $2n$ indeterminates, and the matrix $J_{2n}$ of all ones of the same size, let
• $h_1(A, \mathbf{z}) = \mathrm{haf}(Z_{2n}J_{2n} + J_{2n}Z_{2n} + A) = \mathrm{haf}(z_i + z_j + a_{ij})$,

• $h_2(A, \mathbf{z}) = \mathrm{haf}(Z_{2n}J_{2n} + A) = \mathrm{haf}(z_i + a_{ij})$.

• $h_3(A, \mathbf{z}) = \mathrm{haf}(Z_{2n}J_{2n}Z_{2n} + A) = \mathrm{haf}(z_i z_j + a_{ij})$,

For convenience, we also provided a shorthand for these matrices that is sometimes easier to work with. The motivation behind the definition of these multivariate graph polynomials is the following.

**Proposition 3.5** Let A be a monotone hook matrix. Assume that either

1. $h_1(A, \mathbf{z})$ is stable, or

2. $h_2(A, \mathbf{z})$ is stable, or

3. $h_3(A, \mathbf{z})$ is Hurwitz-stable.

Then the conclusion of the MHH conjecture (Conjecture 1.1) holds for the matrix A.

Unfortunately, these generalizations fail to be stable even for $\{0, 1\}$ matrices.

**Proposition 3.6** There is a monotone hook $\{0, 1\}$ matrix A for which $h_1(A, \mathbf{z})$ is not stable, and $h_2(A, \mathbf{z})$ is not stable, and $h_3(A, \mathbf{z})$ is not Hurwitz-stable.

Since all these polynomials are multi-affine (they have degree at most one in each variable) we can use the following criterion (Theorem 5.6 in Brändén (2007)) to check whether they are stable or not.

**Theorem 3.7** A multi-affine polynomial $f \in \mathbb{R}[z_1, \dots, z_n]$ is stable if and only if

$$ \Delta_{i,j} f := \frac{\partial f}{\partial z_i}(x) \cdot \frac{\partial f}{\partial z_j}(x) - \frac{\partial^2 f}{\partial z_i \partial z_j}(x) \cdot f(x) \ge 0 $$

for all $x \in \mathbb{R}^n$ and $1 \le i, j \le n$.

**Proof of Proposition 3.6:** Let

$$ A = \begin{pmatrix} * & 0 & 0 & 1 \\ 0 & * & 1 & 1 \\ 0 & 1 & * & 1 \\ 1 & 1 & 1 & * \end{pmatrix}, $$

where * denotes a wildcard, since the hafnian does not depend on the diagonal elements.

We have that

$$ h_1(A, \mathbf{z}) = (z_1 + z_2)(z_3 + z_4 + 1) + (z_1 + z_3)(z_2 + z_4 + 1) + (z_1 + z_4 + 1)(z_2 + z_3 + 1) $$

and from this we get that $\Delta_{3,4}h_1(A, \mathbf{z}) = 4z_1^2 + 4z_2^2 + 4z_1z_2 + 2z_2$ which can take on negative values (e.g., when $z_1 = 0$ and $-1/2 < z_2 < 0$). Similarly, one can easily check that $\Delta_{1,3}h_2(A, \mathbf{z}) = -z_2 - 1$. Checking Hurwitz-stability for $h_3(A, z_1, z_2, z_3, z_4)$ can be reduced to checking stability for $\tilde{h}_3(A, \mathbf{z}) = h_3(A, \frac{z_1}{i}, \frac{z_2}{i}, \frac{z_3}{i}, \frac{z_4}{i})$ because multiplication by the imaginary unit $i$ maps the right half-plane to the upper half-plane. Since $\tilde{h}_3(A, \mathbf{z})$ has only real coefficients we can apply Brändén's criterion again to get that

$$ \Delta_{3,4} \tilde{h}_3(A, \mathbf{z}) = z_1(9z_1z_2^2z_3z_4 + 3z_1z_2z_3 + 3z_2^2z_3 + 3z_1z_2z_4 + z_1 - 2z_2) $$

an expression that takes on negative values as well (e.g., when $z_1 = z_2 = 1$ and $z_3 = z_4 = 0$). $\square$
# 4 An alternative proof for a subclass of threshold graphs

In this section, we make use of the $\alpha$-permanents and their close connections to hafnians to prove that $\text{haf}(zJ + A)$ has only real roots for certain $\{0, 1\}$ matrices $A$ of a special form.

Recall the definition of $\alpha$-permanent of an $n \times n$ matrix $B = (b_{ij})$ (Vere-Jones (1998)):

$$ \text{per}(B; \alpha) = \sum_{\pi \in \mathcal{S}_n} \alpha^{\nu(\pi)} \prod_{i=1}^{n} b_{i, \pi(i)}, \qquad (7) $$

where $\nu(\pi)$ is the number of disjoint cycles of the permutation $\pi$. Special cases of this formula when $\alpha = 1$ and when $\alpha = -1$ yield $\text{per}(B)$ and $(-1)^n \det(B)$, respectively.

It is known that for real symmetric $n \times n$ matrices $B$:

$$ \text{per}(B; 1/2) = \frac{1}{2^n} \text{haf} \begin{pmatrix} B & B \\ B & B \end{pmatrix}. \qquad (8) $$

The combinatorial proof of (8) in Frenkel (2010) allows us to easily extend this equality to any symmetric matrix $B$ (i.e., the entries need not be real numbers, they can be indeterminates as well). We combine this result with the cycle-counting extension of the MCP theorem (Proposition 4.4 of Brändén et al. (2010)). In fact, we only need the following bivariate special case of it (when we diagonalize all $x_i = x$ and $y_i = y$):

**Proposition 4.1** Let $F$ be an $n \times n$ Ferrers matrix, a $\{0, 1\}$ matrix that is weakly decreasing down columns and weakly increasing from left to right across rows. Then, for any $\alpha > 0$, the polynomial $\text{per}(xF + y(J_n - F); \alpha) \in \mathbb{R}[x, y]$ is stable.

**Corollary 4.2** Let $B$ be an $n \times n$ symmetric monotone column $\{0, 1\}$ matrix, and let $A = \begin{pmatrix} B & B \\ B & B \end{pmatrix}$ then the polynomial $\text{haf}(zJ_{2n} + A)$ has only real roots.

**Proof:** From (8) we see that it is equivalent to prove that the $1/2$-permanent of $zJ_n + B$ has real roots only. Since $B$ is a symmetric monotone column $\{0, 1\}$ matrix, it is also a Ferrers matrix, and thus we can apply Proposition 4.1 to it with $\alpha = 1/2$. Translation and diagonalization preserve stability (see Lemma 2.1), so by setting $x = z + 1$ and $y = z$ we get that $\text{per}(zJ_n + B; 1/2)$ is stable, i.e., has real roots only. $\square$

**Remark 4.3** The adjacency matrices of the form $A = \begin{pmatrix} B & B \\ B & B \end{pmatrix}$ where $B$ is a symmetric is usually not a monotone hook matrix. However, it can be shown that for any such matrix $A$ there is a threshold with adjacency matrix equal to $A$. In other words, Corollary 4.2 is a special case of Theorem 3.1.

# Acknowledgment

I thank my advisor, Jim Haglund for his guidance and support, and also Petter Brändén for his suggestions and Paul Levande for helpful discussions.
References

J. Borcea and P. Brändén. The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability. *Invent. Math.*, 177(3):541–569, September 2009. URL http://dx.doi.org/10.1007/s00222-009-0189-3.

J. Borcea and P. Brändén. Multivariate Pólya–Schur classification problems in the Weyl algebra. *Proc. London Math. Soc.*, 101(1):73–104, July 2010. URL http://dx.doi.org/10.1112/plms/pdp049.

P. Brändén. Polynomials with the half-plane property and matroid theory. *Adv. Math.*, 216(1):302–320, December 2007. URL http://dx.doi.org/10.1016/j.aim.2007.05.011.

P. Brändén, J. Haglund, M. Visontai, and D. G. Wagner. The proof of the monotone column permanent conjecture. Submitted. Preprint available at http://arxiv.org/abs/1010.2565v2, 2010.

E. R. Caianiello. *Combinatorics and renormalization in quantum field theory*. Frontiers in Physics. W. A. Benjamin, Reading, Mass., 1973.

S. Fisk. Polynomials, roots, and interlacing. Available at http://arxiv.org/abs/math/0612833, 2008.

P. E. Frenkel. Remarks on the α-permanent. *Math. Res. Lett.*, 17(4):795–802, 2010. URL http://www.mathjournals.org/mrl/2010-017-004/2010-017-004-017.html.

J. Haglund. Further investigations involving rook polynomials with only real zeros. *Europ. J. Combin.*, 21(8):1017–1037, November 2000. URL http://dx.doi.org/10.1006/eujc.2000.0422.

N. V. R. Mahadev and U. N. Peled. *Threshold graphs and related topics*, volume 56 of *Annals of Discrete Mathematics*. Elsevier, Amsterdam, 1995.

D. Vere-Jones. A generalization of permanents and determinants. *Linear Alg. Appl.*, 111:119–124, December 1998. URL http://dx.doi.org/10.1016/0024-3795(88)90053-5.

D. G. Wagner. Multivariate stable polynomials: theory and applications. *Bull. Amer. Math. Soc.*, 48:53–84, 2011. URL http://dx.doi.org/10.1090/S0273-0979-2010-01321-5.