GENERALIZED MATRIX POLYNOMIALS OF TREE LAPLACIANS INDEXED BY SYMMETRIC FUNCTIONS AND THE GTS POSET

MUKESH KUMAR NAGAR AND SIVARAMAKRISHNAN SIVASUBRAMANIAN

Abstract. Let T be a tree on n vertices with Laplacian matrix L_{T} and q-Laplacian L_{T}^{q}. Let GTS_{n} be the generalized tree shift poset on the set of unlabelled trees on n vertices. Inequalities are known between coefficients of the immanantal polynomial of L_{T} and L_{T}^{q} as one moves up the poset GTS_{n}. Using the Frobenius characteristic, this can be thought as a result involving the Schur symmetric function s_{λ}. In this paper, we use an arbitrary symmetric function to define a generalized matrix function of an n × n matrix. When the symmetric function is the monomial and the forgotten symmetric function, we generalize such inequalities among coefficients of the generalized matrix polynomial of L_{T}^{q} as one moves up the GTS_{n} poset.

1. Introduction

For a positive integer n, let [n] = {1, 2, …, n} and let 𝔖_{n} denote the symmetric group on the set [n]. We denote partitions λ of the number n as λ ⊢ n. We write partitions using the exponential notation, with multiplicities of parts written as exponents. For λ ⊢ n, let χ_{λ} be the irreducible character of 𝔖_{n} over ℂ indexed by λ. We think of χ_{λ} as a function χ_{λ} : 𝔖_{n} ↦ ℤ. With respect to an irreducible character χ_{λ}, define the immanant of the n × n matrix A = (a_{i,j})_{1≤i,j≤n} as

(1)  d_{λ}(A) = ∑_{ψ∈𝔖_{n}} χ_{λ}(ψ) ∏_{i=1}^{n} a_{i,ψ(i)}.

Let Λ_{ℚ}^{n} denote the vector space of degree n symmetric functions with coefficients from ℚ. The set of monomial symmetric functions {m_{λ}}_{λ⊢n} is one of the well known bases of Λ_{ℚ}^{n}. We refer the reader to the books by Stanley [14] and by Mendes and Remmel [9] for background on symmetric functions. Λ_{ℚ}^{n} actually has an inner product structure as well. Another inner product space often studied is CF_{n}, the space of class functions from 𝔖_{n} ↦ ℚ. Further, there is a well known isometry between these two spaces called the Frobenius characteristic, denoted ch : CF_{n} → Λ_{ℚ}^{n} (see Stanley [14] for more details).

Let γ ∈ Λ_{ℚ}^{n} and consider Γ_{γ} = ch^{−1}(γ) its inverse Frobenius image. Clearly, Γ_{γ} ∈ CF_{n} is a class function indexed by γ. Define the generalized matrix function (GMF henceforth) of an n × n matrix A with respect to γ as

(2)  d_{γ}(A) = ∑_{ψ∈𝔖_{n}} Γ_{γ}(ψ) ∏_{i=1}^{n} a_{i,ψ(i)}.

2010 Mathematics Subject Classification. 05C05, 06A06, 15A15.

Key words and phrases. Tree, GTS_{n} poset, Laplacian, monomial symmetric function, generalized matrix polynomial.

Define the generalized matrix polynomial ζ_{γ}^{A}(x) of A in a new variable x with respect to a symmetric function γ as follows: ζ_{γ}^{A}(x) = d_{γ}(xI − A). It is well known that the inverse Frobenius image ch^{−1}(s_{λ}) of the Schur symmetric function s_{λ} is χ_{λ}, the irreducible character of 𝔖_{n} over ℂ indexed by λ (see [14]). Thus, from (1) and (2), we can see that d_{s_{λ}}(A) = d_{λ}(A) and ζ_{s_{λ}}^{A}(x) = d_{λ}(xI − A).

Csikvári in [5] defined a poset on the set of unlabelled trees with n vertices that we denote in this paper as GTS_{n}. Among other results, he showed that if one moves up along the GTS_{n} poset, all coefficients of the characteristic polynomial of the Laplacian matrix L_{T} of a tree T decrease in absolute value. This result was generalized by Nagar and Sivasubramanian in [12] to immanantal polynomials of L_{T}^{q} indexed by any λ ⊢ n, where L_{T}^{q} is the q-Laplacian matrix of T (see Theorem 7).

Let ℝ^{+} denote the set of non-negative real numbers and ℝ^{+}[q^{2}] denote the set of polynomials in q^{2} with coefficients in ℝ^{+}. Let m_{λ} ∈ Λ_{ℚ}^{n} be the monomial symmetric function indexed by λ ⊢ n. In Section 4 of this paper, we prove the following result which shows monotonicity of the coefficient of (−1)^{r}x^{n−r} for 0 ≤ r ≤ n in ζ_{m_{λ}}^{L_{T}^{q}}(x) when we move up along GTS_{n}.

Theorem 1. Let T_{1} and T_{2} be two trees with n vertices such that T_{2} covers T_{1} in GTS_{n}. Let L_{T_{1}}^{q} and L_{T_{2}}^{q} be the q-Laplacians of T_{1} and T_{2} respectively. For λ ⊢ n, let

ζ_{m_{λ}}^{L_{T_{1}}^{q}}(x) = d_{m_{λ}}(xI − L_{T_{1}}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{m_{λ},r}^{L_{T_{1}}^{q}}(q)x^{n−r} and

ζ_{m_{λ}}^{L_{T_{2}}^{q}}(x) = d_{m_{λ}}(xI − L_{T_{2}}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{m_{λ},r}^{L_{T_{2}}^{q}}(q)x^{n−r}.

Then for all λ ⊢ n, we have c_{m_{λ},r}^{L_{T_{1}}^{q}}(q) − c_{m_{λ},r}^{L_{T_{2}}^{q}}(q) ∈ ℝ^{+}[q^{2}], where 0 ≤ r ≤ n. Further if λ ≠ 2^{k}, 1^{n−2k} ⊢ n, then, d_{m_{λ}}(xI − L_{T_{1}}^{q}) = d_{m_{λ}}(xI − L_{T_{2}}^{q}) = 0.

Recall that for γ ∈ Λ_{ℚ}^{n}, Γ_{γ} = ch^{−1}(γ). For the proof of Theorem 1, we show the following lemma involving Γ_{m_{λ}} = ch^{−1}(m_{λ}) and binomial coefficients. Let Γ_{γ}(j) denote the class function Γ_{γ}(·) evaluated at a permutation ψ ∈ 𝔖_{n} with cycle type 2^{j}, 1^{n−2j}. For 0 ≤ i ≤ ⌊n/2⌋, define

(3)  α_{i}(γ) = ∑_{j=0}^{i} \binom{i}{j}Γ_{γ}(j).

In Section 4, we prove the following lemma which we believe is of independent interest.

Lemma 2. For all λ ⊢ n and for 0 ≤ i ≤ ⌊n/2⌋, α_{i}(m_{λ}) = 2^{i} if λ = 2^{i}, 1^{n−2i} and 0 otherwise.

In Section 5 we consider the generalized matrix polynomial of L_{T}^{q} with respect to the forgotten symmetric function. Our main result of that section is Theorem 20, where we show similar monotonicity results as we move on the GTS_{n} poset.

2. Preliminaries

We now give some motivational background for our results and place it in its context. The

normalized immanant of a matrix A corresponding to a partition λ is defined as \overline{d}_{λ}(A) = \frac{d_{λ}(A)}{χ_{λ}(id)}.

Here, χ_{λ}(id) equals the dimension of the irreducible representation of 𝔖_{n} over ℂ indexed by λ.

Schur [13] showed that among normalized immanants, the determinant is the smallest normalized immanant for any positive semidefinite Hermitian matrix. This shows that for any positive semidefinite Hermitian matrix A, all its normalized immanants (and hence immanants) are nonnegative. Though the immanant d_{λ}(A) is non-negative, (1) is not a non-negative expression for d_{λ}(A) as χ_{λ}(ψ) ∏_{i=1}^{n} a_{i,ψ(i)} is not necessarily non-negative for all ψ ∈ 𝔖_{n} that contribute to d_{λ}(A).

Recall that the Laplacian matrix L_{G} of a graph G is defined as L_{G} = D − A, where D is the diagonal matrix with degrees of G on the diagonal and A is the adjacency matrix of G. It is well known that L_{G} is positive semidefinite for all graphs G (see [8]). When the matrix A is the Laplacian L_{T} of a tree T, then Chan and Lam in [4] gave the following two results which give an alternate positive expression for the immanant d_{λ}(L_{T}).

We denote the number of parts of a partition λ of n as l(λ). For λ ⊢ n, let χ_{λ}(j) denote the character value χ_{λ}(·) evaluated at a permutation ψ ∈ 𝔖_{n} with cycle type 2^{j}, 1^{n−2j}. For 0 ≤ i ≤ ⌊n/2⌋ and λ ⊢ n, define

(4)  α_{i,λ} = ∑_{j=0}^{i} \binom{i}{j}χ_{λ}(j).

Lemma 3 (Chan and Lam, [3]). For all λ ⊢ n and for 0 ≤ i ≤ ⌊n/2⌋, the quantity α_{i,λ} is a non-negative integral multiple of 2^{i}. Moreover for 1 ≤ i ≤ ⌊n/2⌋, α_{i,λ} = 0 if and only if l(λ) > n − i.

Theorem 4 (Chan and Lam, [4]). Let L_{T} be the Laplacian matrix of a tree T on n vertices. Then, for all λ ⊢ n, d_{λ}(L_{T}) = ∑_{i=0}^{⌊n/2⌋} α_{i,λ}a_{i}(T), where a_{i}(T) equals the number of vertex orientations with exactly i bidirected edges (and is hence a non-negative integer for all i).

Lemma 3 and Theorem 4 make it clear that all immanants of L_{T} are non-negative. Similar results are known for the q-Laplacian of T (see Theorem 5). Define L_{G}^{q} = I + q^{2}(D − I) − qA as the q-Laplacian of a graph G, where D and A are as before and I is the identity matrix. Here q is a variable. It is easy to see that setting q = 1 in L_{G}^{q} gives us the usual combinatorial Laplacian L_{G}. The matrix L_{G}^{q} has appeared in the contexts of Ihara–Selberg zeta functions of graphs G (see Bass [2] and Foata and Zeilberger [7]). When the graph G is a tree T, L_{T}^{q} has connections with the inverse of the exponential distance matrix of T (see Bapat, Lal and Pati [1] and Nagar [10]). Nagar and Sivasubramanian in [11] gave the following q-analogue of Theorem 4 involving L_{T}^{q}. To state it, we need a q-analogue of the term a_{i}(T). We describe it briefly and refer the reader to [11] for more details. Let O_{i}(T) denote the set of vertex orientations in T with i bidirected edges, and let a_{i}(T) = |O_{i}(T)|. A statistic Lexaway : O_{i}(T) ↦ ℤ_{≥0} was defined in [11]. Using it, when i ≥ 1, the following q-analogue a_{i}(T, q) of a_{i}(T) was defined (see [11, Corollary 9]):

(5)  a_{i}(T, q) = ∑_{O∈O_{i}} q^{Lexaway(O)}.

In [11], we had also defined a_{0}(T, q) = 1 − q^{2}. It turns out that for all i ≥ 0, the a_{i}(T, q) is a polynomial in q^{2} (see [11, Remark 15]). With this definition, we can state a q-analogue of Theorem 4.

Theorem 5 (Nagar and Sivasubramanian). Let L_{T}^{q} be the q-Laplacian matrix of a tree T on n vertices. Then, for all λ ⊢ n, d_{λ}(L_{T}^{q}) = ∑_{i=0}^{⌊n/2⌋} α_{i,λ}a_{i}(T, q), where the a_{i}(T, q) is defined in (5).

Clearly, setting q = 1 in L_{T}^{q} gives L_{T} and setting q = 1 in a_{i}(T, q) gives a_{i}(T) for i with 0 ≤ i ≤ ⌊n/2⌋. Extensions of Theorem 5 to the bivariate q, t-Laplacian denoted as L_{T}^{q,t} were also given in [11]. Later, in [12], the following more general result about the coefficient of (−1)^{r}x^{n−r} in the immanantal polynomial d_{λ}(xI −L_{T}^{q}) was proved. To state it, we need polynomials a_{i,r}(T, q) which generalize a_{i}(T, q). Let B ⊂ V (T) be a subset of the vertex set of T with |B| = r, where r ≤ n. Let O_{B,i}^{T} be the set of vertex orientations of vertices in B that have i bidirected edges. There is a statistic Aw_{B}^{T} : O_{B,i}^{T} ↦ ℤ_{≥0} with respect to which we define

(6)  a_{i,r}(T, q) = ∑_{B⊆V (T),|B|=r} ∑_{O∈O_{B,i}^{T}} q^{Aw(_{B}^{T}(O)}.

With this definition, we have the following [12, Lemma 7, Corollary 12].

Lemma 6 (Nagar and Sivasubramanian). Let T be a tree on n vertices with q-Laplacian L_{T}^{q}. For λ ⊢ n, let d_{λ}(xI − L_{T}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{λ,r}^{L_{T}^{q}}(q)x^{n−r}. Then for 0 ≤ r ≤ n, we have

c_{λ,r}^{L_{T}^{q}}(q) = ∑_{i=0}^{⌊r/2⌋} α_{i,λ}a_{i,r}(T, q).

In Lemma 6, one can get the immanant d_{λ}(L_{q}^{T}) as the constant term of the immanantal polynomial (that is, by looking at the special case when r = n). Thus, Lemma 6 generalizes Theorem 5. Using Lemma 6, the following result about monotonicity for the coefficients of all immanantal polynomials of L_{T}^{q} along GTS_{n} was proved in [12, Theorem 1].

Theorem 7 (Nagar and Sivasubramanian). Let T_{1} and T_{2} be two trees with n vertices such that T_{2} covers T_{1} in GTS_{n}. Let L_{T_{1}}^{q} and L_{T_{2}}^{q} be the q-Laplacians of T_{1} and T_{2} respectively. For λ ⊢ n, let

ζ_{s_{λ}}^{L_{T_{1}}^{q}}(x) = d_{λ}(xI − L_{T_{1}}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{λ,r}^{L_{T_{1}}^{q}}(q)x^{n−r} and

ζ_{s_{λ}}^{L_{T_{2}}^{q}}(x) = d_{λ}(xI − L_{T_{2}}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{λ,r}^{L_{T_{2}}^{q}}(q)x^{n−r}.

Then for all λ ⊢ n, we have c_{λ,r}^{L_{T_{1}}^{q}}(q) − c_{λ,r}^{L_{T_{2}}^{q}}(q) ∈ ℝ^{+}[q^{2}], where 0 ≤ r ≤ n.

The proof of Theorem 7 required to give a combinatorial expression for the coefficients c_{λ,r}^{L_{T_{1}}^{q}}(q)

and c_{λ,r}^{L_{T_{2}}^{q}}(q) (see Lemma 6) and then to give an injection between the objects counting c_{λ,r}^{L_{T_{2}}^{q}}(q) and

those counting c_{λ,r}^{L_{T_{1}}^{q}}(q) (see Lemma 11).

3. GMF of q-Laplacians arising from symmetric functions

Let Γ_{γ} = ch^{−1}(γ) be the inverse Frobenius image of the symmetric function γ ∈ Λ_{ℚ}^{n}. Note that Γ_{γ} is a class function of 𝔖_{n} over ℂ indexed by γ. Plugging the matrix L_{T}^{q} = (l_{i,j}^{q})_{1≤i,j≤n} in (2), we get

(7)  d_{γ}(L_{T}^{q}) = ∑_{ψ∈𝔖_{n}} Γ_{γ}(ψ) ∏_{i=1}^{n} l_{i,ψ(i)}^{q}.

For the matrix L_{T}^{q}, it is very easy to show the following counterpart of Theorem 5, where we change the Frobenius inverse of the Schur symmetric function to the Frobenius inverse of an arbitrary symmetric function. We recall the polynomial a_{i}(T, q) from (5) and α_{i}(γ) from (3). We start with the following result. As its proof is a verbatim copy of the proof of Theorem 5, with the only change being that we replace α_{i,λ} by α_{i}(γ), we omit it.

Theorem 8. Let L_{T}^{q} be the q-Laplacian matrix of a tree T on n vertices. Then, for all γ ∈ Λ_{ℚ}^{n}, d_{γ}(L_{T}^{q}) = ∑_{i=0}^{⌊n/2⌋} α_{i}(γ)a_{i}(T, q).

It is very simple to show the following counterpart of Lemma 6. Recall the polynomial a_{i,r}(T, q) from (6). Since the proof is identical, we omit it and merely state the result.

Lemma 9. Let T be a tree on n vertices with q-Laplacian L_{T}^{q}. Then for all γ ∈ Λ_{ℚ}^{n}, we have

d_{γ}(xI − L_{T}^{q}) = ∑_{r=0}^{n}(−1)^{r}c_{γ,r}^{L_{T}^{q}}(q)x^{n−r}, where c_{γ,r}^{L_{T}^{q}}(q) = ∑_{i=0}^{⌊r/2⌋} α_{i}(γ)a_{i,r}(T, q) for 0 ≤ r ≤ n.

Every element γ ∈ Λ_{ℚ}^{n} is written as a linear combination of basis vectors of Λ_{ℚ}^{n}. The vector space Λ_{ℚ}^{n} has six standard bases. We use standard terminology to denote each of the usual bases of Λ_{ℚ}^{n}. Thus, s_{λ}, p_{λ}, e_{λ}, h_{λ}, m_{λ} and f_{λ} denote the Schur, power sum, elementary, homogeneous, monomial and forgotten symmetric functions respectively. The inverse Frobenius map of each of these will be denoted by the same letter, but in capital font and with the partition λ as a superscript rather than a subscript. Thus, E^{λ} = ch^{−1}(e_{λ}), χ_{λ} = S^{λ} = ch^{−1}(s_{λ}) and so on.

As mentioned earlier, the inverse Frobenius image ch^{−1}(s_{λ}) of the Schur symmetric function s_{λ} is χ_{λ}, the irreducible character of 𝔖_{n} over ℂ indexed by λ. Therefore the identity given in (4) is a special case of the identity given in (3) when γ = s_{λ}. Thus, if any symmetric function γ ∈ Λ_{ℚ}^{n} is Schur-positive (that is, γ = ∑_{λ⊢n} a_{λ}s_{λ} where a_{λ} ∈ ℝ^{+} for all λ ⊢ n), then, by linearity, Lemma 3 will be true with χ_{λ} replaced by ch^{−1}(γ) in (4). Unfortunately, the monomial symmetric function m_{λ} indexed by λ is not Schur-positive. Thus, if M^{λ} = ch^{−1}(m_{λ}), it is not clear that Lemma 3 with χ_{λ} replaced by M^{λ} in (4) is true.

For γ ∈ Λ_{ℚ}^{n}, let Γ_{γ} = ch^{−1}(γ). Thus, if Γ_{γ}(j) ≥ 0 for all j, then from (3), we get α_{i}(γ) ≥ 0. Since the inverse Frobenius image Γ_{p_{λ}} of p_{λ} is a scalar multiple of the indicator function of the conjugacy class C_{λ} indexed by λ (see [14]), it follows that α_{i}(p_{λ}) ≥ 0 for all λ ⊢ n and for all i = 0, 1, …, ⌊n/2⌋.

As mentioned earlier, if γ ∈ Λ_{ℚ}^{n} is Schur-positive, then α_{i}(γ) ≥ 0. Since h_{λ} is Schur-positive (see [14, Corollary 7.12.4]), it follows from Lemma 3 that α_{i}(h_{λ}) ≥ 0 for all λ ⊢ n. Similarly, it is well known that e_{λ} is also Schur-positive. Thus α_{i}(e_{λ}) ≥ 0 for all λ ⊢ n. We record these facts below for future use.

Lemma 10. For all λ ⊢ n and for 0 ≤ i ≤ ⌊n/2⌋, we have α_{i}(γ) ≥ 0 for γ ∈ {p_{λ}, h_{λ}, e_{λ}}.

Let the tree T have n vertices and, for 0 ≤ i, r ≤ n, let a_{i,r}(T, q) = a_{i,r}^{T}(q) be the polynomial in q^{2} with non-negative real coefficients, defined by Nagar and Sivasubramanian in [12, page 7]. They showed the following result (see [12, Lemma 19, 23 and Corollary 22]).

Lemma 11 (Nagar and Sivasubramanian). Let T_{1} and T_{2} be two trees with n vertices such that T_{2} covers T_{1} in GTS_{n}. Then for all 0 ≤ i, r ≤ n, we have a_{i,r}(T_{1}, q) − a_{i,r}(T_{2}, q) ∈ ℝ^{+}[q^{2}].

With Lemma 10 and Lemma 11 in place, we can get the following Corollary. Its proof mimics the proof of Theorem 7.

Corollary 12. Theorem 7 is true when we replace the immanantal polynomial d_{λ}(xI −L_{T_{j}}^{q}) by the generalized matrix polynomials d_{γ}(xI − L_{T_{j}}^{q}) for γ ∈ {p_{λ}, h_{λ}, e_{λ}} and for j = 1, 2.

By Theorem 7 and Corollary 12, we thus have monotonicity results about four of the six standard bases, as we move up on GTS_{n}. This paper plugs the gaps left by considering the generalized matrix polynomials of L_{T}^{q} arising from the last two bases m_{λ} and f_{λ}. In other words, we consider the cases when we replace the immanantal polynomial d_{λ}(xI − L_{T_{j}}^{q}) by d_{g}(xI − L_{T_{j}}^{q}) when g ∈ {m_{λ}, f_{λ}} in Theorem 7.

4. GMF of tree Laplacians arising from m_{λ}, the monomial symmetric function

We prove Theorem 1 in this section. We need the notion of λ-brick tabloids of shape μ which is used to give a combinatorial interpretation of the quantity Γ_{m_{λ}}(ψ) = M^{λ}(ψ), where λ, μ ⊢ n and ψ ∈ 𝔖_{n}. We recall the following definition of λ-brick tabloid of shape μ defined by Eğecioğlu and Remmel in [6].

Definition 13. Let λ ⊢ n with λ = λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{l(λ)}. Let μ ⊢ n and let F_{μ} be its Ferrers diagram. A λ-brick tabloid B_{λ,μ} of shape μ is a filling of F_{μ} with bricks b_{1}, b_{2}, …, b_{l(λ)} of size λ_{1}, λ_{2}, …, λ_{l(λ)} respectively such that brick b_{i} covers exactly λ_{i} squares of F_{μ} all of which lie in a single row of F_{μ} and no two bricks overlap. Here, bricks of the same size are indistinguishable.

We refer the reader to the book by Mendes and Remmel [9, Chapter 2] for an introduction to λ-brick tabloids. Given a brick b in B_{λ,μ}, let |b| denote the length of b. Define wt_{B_{λ,μ}}(b) to be |b| if b is at the end of a row in B_{λ,μ} and 1 otherwise. We next define a weight w(B_{λ,μ}) for each λ-brick tabloid B_{λ,μ} of shape μ as follows:

w(B_{λ,μ}) = ∏_{b∈B_{λ,μ}} wt_{B_{λ,μ}}(b).

In other words, w(B_{λ,μ}) is the product of the lengths of the rightmost brick in each row of B_{λ,μ}. For λ, μ ⊢ n, let BT_{λ,μ} be the set of all λ-brick tabloids of shape μ. For λ ⊢ n and for ψ ∈ 𝔖_{n}, Eğecioğlu and Remmel in [6, Theorem 1] gave the following combinatorial interpretation of M^{λ}(ψ) which we need.

Theorem 14 (Eğecioğlu and Remmel). For λ ⊢ n, let M^{λ} = ch^{−1}(m_{λ}). When a permutation ψ ∈ 𝔖_{n} has cycle type μ, then

M^{λ}(ψ) = (−1)^{l(λ)−l(μ)} ∑_{B_{λ,μ}∈BT_{λ,μ}} w(B_{λ,μ}).

We say λ is a refinement of μ if the parts μ_{i} of μ can be obtained as a disjoint union of the parts λ_{j} of λ. From the definition of B_{λ,μ}, it is easy to see that if λ is not a refinement of μ, then BT_{λ,μ} = ∅. Thus M^{λ}(ψ) = 0, unless when λ refines the cycle type μ of ψ. Let M^{λ}(j) denote the value of the function M^{λ}(·) evaluated at a permutation ψ ∈ 𝔖_{n} with cycle type 2^{j}, 1^{n−2j}. We start with the following simple consequence of Theorem 14,

Corollary 15. Let λ ⊢ n and let ψ ∈ 𝔖_{n} be a permutation with cycle type μ = 2^{j}, 1^{n−2j}. Then,

M^{λ}(j) = \begin{cases}(−1)^{j−k}2^{k}\binom{j}{k}, & ifλ = 2^{k}, 1^{n−2k} and k ≤ j, \\ 0, & otherwise. \end{cases}

Proof. We divide the proof into two cases when λ is a refinement of μ and when it is not. If λ is a refinement of μ, then we must have λ = 2^{k}, 1^{n−2k} for some k with 0 ≤ k ≤ j. In this case, all the k bricks of length 2 must be placed in some of the k rows from the first j rows of F_{μ}. Thus, the number of such λ-brick tabloids B_{λ,μ} of shape μ is \binom{j}{k}, and each B_{λ,μ} contributes the weight 2^{k} in the summation of Theorem 14. Thus, the total contribution in M^{λ}(j) is 2^{k}\binom{j}{k} and l(λ) − l(μ) = j − k. Hence M^{λ}(j) = (−1)^{j−k}2^{k}\binom{j}{k}.

When λ is not a refinement of μ, by Theorem 14, M^{λ}(j) = 0, completing the proof. □

We next prove Lemma 2 which says that for all λ ⊢ n and for 0 ≤ i ≤ ⌊n/2⌋, the quantity α_{i}(m_{λ}) is a non-negative integral multiple of 2^{i}. We will need the following very easy identity involving binomial coefficients \binom{j}{k}\binom{i}{j} = \binom{i−k}{j−k}\binom{i}{k}.

Proof of Lemma 2. By Corollary 15, when λ ≠ 2^{k}, 1^{n−2k}, M^{λ}(j) = 0 for all j. Thus, from (3), α_{i}(m_{λ}) = 0 for 0 ≤ i ≤ ⌊n/2⌋. When λ = 2^{k}, 1^{n−2k} ⊢ n for some k with 0 ≤ k ≤ ⌊n/2⌋, by Corollary 15, we see that

α_{i}(m_{λ}) = ∑_{j=0}^{i} M^{λ}(j)\binom{i}{j} = ∑_{j=0}^{i}(−1)^{j−k}2^{k}\binom{j}{k}\binom{i}{j}

= 2^{k}\binom{i}{k} ∑_{j=k}^{i}(−1)^{j−k}\binom{i − k}{j − k} = \begin{cases}2^{i}, & if i = k, \\ 0, & otherwise. \end{cases}

The proof is complete. □

Using Lemmas 2 and 11, we can now prove Theorem 1.

Proof of Theorem 1. From Lemmas 2 and 9, for 0 ≤ r ≤ n and for j = 1, 2, it is simple to see that the coefficient of (−1)^{r}x^{n−r} in d_{m_{λ}}(xI − L_{T_{j}}^{q}) is given by

(8) c_{m_{λ},r}^{L_{T_{j}}^{q}}(q) = ∑_{i=0}^{⌊r/2⌋} α_{i}(m_{λ})a_{i,r}(T_{j}, q) = \begin{cases}2^{k}a_{k,r}(T_{j}, q), & if λ = 2^{k}, 1^{n−2k} and k ≤ ⌊r/2⌋, \\ 0, & otherwise. \end{cases}

By Lemma 11 and (8), we get c_{m_{λ},r}^{L_{T_{1}}^{q}}(q) − c_{m_{λ},r}^{L_{T_{2}}^{q}}(q) ∈ ℝ^{+}[q^{2}] for all λ ⊢ n and for 0 ≤ r ≤ n. Furthermore, if λ ≠ 2^{k}, 1^{n−2k} ⊢ n for all k, then from (8), the coefficient of (−1)^{r}x^{n−r} in d_{m_{λ}}(xI − L_{T_{j}}^{q}) is zero for 0 ≤ r ≤ n and j = 1, 2. The proof is complete. □

Thus, for all λ ⊢ n and for all q ∈ ℝ, moving up on GTS_{n} decreases the coefficient of (−1)^{r}x^{n−r} in d_{m_{λ}}(xI − L_{T}^{q}), where 0 ≤ r ≤ n. Consequently, for all positive integers n, this monotonicity result on GTS_{n} shows that the max-min pair of these coefficients is (P_{n}, S_{n}), where P_{n} and S_{n} are the path tree and the star tree on n vertices respectively. The following example illustrates Lemma 2.

Example 16. Let n = 15. For all λ ⊢ n and for all i ∈ {0, 1, 2, 3, 4, 5, 6, 7}, the values of the quantity α_{i}(m_{λ}) are tabulated in Table 1.

\begin{matrix}λ ⊢ n = 15 & i = 0 & i = 1 & i = 2 & i = 3 & i = 4 & i = 5 & i = 6 & i = 7 \\ λ = 1^{15} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ λ = 2, 1^{13} & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ λ = 2^{2}, 1^{11} & 0 & 0 & 4 & 0 & 0 & 0 & 0 & 0 \\ λ = 2^{3}, 1^{9} & 0 & 0 & 0 & 8 & 0 & 0 & 0 & 0 \\ λ = 2^{4}, 1^{7} & 0 & 0 & 0 & 0 & 16 & 0 & 0 & 0 \\ λ = 2^{5}, 1^{5} & 0 & 0 & 0 & 0 & 0 & 32 & 0 & 0 \\ λ = 2^{6}, 1^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 64 & 0 \\ λ = 2^{7}, 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 128 \\ λ ≠ 2^{k}, 1^{n−2k} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

Table 1. The value of α_{i}(m_{λ}).

5. GMF of tree Laplacians arising from f_{λ}, the forgotten symmetric function

Let f_{λ} denote the forgotten symmetric function indexed by λ ⊢ n and let F^{λ} = ch^{−1}(f_{λ}) denote its inverse Frobenius image. This section is devoted to show monotonicity of the coefficient of (−1)^{r}x^{n−r} in ζ_{f_{λ}}^{L_{T}^{q}} (x) = d_{f_{λ}}(xI − L_{T}^{q}) when we move up along GTS_{n}. For this, we need the following combinatorial interpretation of F^{λ}(ψ) by Eğecioğlu and Remmel in [6, Theorem 8].

Theorem 17 (Eğecioğlu and Remmel). Let λ ⊢ n and let ψ ∈ 𝔖_{n} be a permutation with cycle type μ. Then,

F^{λ}(ψ) = (−1)^{n−l(μ)} ∑_{B_{λ,μ}∈BT_{λ,μ}} w(B_{λ,μ}).

For λ ⊢ n, let F^{λ}(j) denote the value of the function F^{λ}(·) evaluated at a permutation ψ ∈ 𝔖_{n} with cycle type 2^{j}, 1^{n−2j}. By Theorem 17, the proof of the following corollary is identical to the proof of Corollary 15, we omit it and merely state the result.

Corollary 18. For λ ⊢ n and for 0 ≤ j ≤ ⌊n/2⌋, we have

F^{λ}(j) = \begin{cases}(−1)^{j}2^{k}\binom{j}{k}, & ifλ = 2^{k}, 1^{n−2k} and k ≤ j, \\ 0, & otherwise. \end{cases}

For a fixed λ ⊢ n, let γ = f_{λ} in (3). We next calculate the quantity α_{i}(f_{λ}) in the following lemma which will be used later in the determination of the coefficient of (−1)^{r}x^{n−r} in d_{f_{λ}}(xI − L_{T}^{q}).

Lemma 19. Let λ ⊢ n. Then for 0 ≤ i ≤ ⌊n/2⌋, we have

α_{i}(f_{λ}) = \begin{cases}(−1)^{i}2^{i}, & ifλ = 2^{i}, 1^{n−2i}, \\ 0, & otherwise. \end{cases}

Proof. By Corollary 18 when λ ≠ 2^{k}, 1^{n−2k}, F^{λ}(j) = 0 for all j. By (3), α_{i}(f_{λ}) = 0 for 0 ≤ i ≤ ⌊n/2⌋. We next assume λ = 2^{k}, 1^{n−2k} ⊢ n for some k with 0 ≤ k ≤ ⌊n/2⌋. In this case, by Corollary 18, we see that

α_{i}(f_{λ}) = ∑_{j=0}^{i} F^{λ}(j)\binom{i}{j} = ∑_{j=0}^{i}(−1)^{j}2^{k}\binom{j}{k}\binom{i}{j}

= 2^{k}\binom{i}{k} ∑_{j=k}^{i}(−1)^{j}\binom{i − k}{j − k} = \begin{cases}(−1)^{i}2^{i}, & if i = k, \\ 0, & otherwise. \end{cases}

All equalities above follow by simple manipulations and hence the proof is complete. □

Theorem 20. Let T be a tree on n vertices with q-Laplacian matrix L_{T}^{q}. Then for 0 ≤ r ≤ n, the coefficient of (−1)^{r}x^{n−r} in d_{f_{λ}}(xI − L_{T}^{q}) is given by

c_{f_{λ},r}^{L_{T}^{q}}(q) = \begin{cases}(−1)^{k}2^{k}a_{k,r}(T, q), & ifλ = 2^{k}, 1^{n−2k} withk ≤ ⌊r/2⌋, \\ 0, & otherwise. \end{cases}

Furthermore, for all λ ⊢ n and all q ∈ ℝ, moving up on GTS_{n} decreases c_{f_{λ},r}^{L_{T}^{q}}(q) in absolute value.

Proof. From Lemmas 9 and 19, it is simple to see that

c_{f_{λ},r}^{L_{T}^{q}}(q) = ∑_{i=0}^{⌊r/2⌋} α_{i}(f_{λ})a_{i,r}(T, q) = \begin{cases}(−1)^{k}2^{k}a_{k,r}(T, q), & if λ = 2^{k}, 1^{n−2k} and k ≤ ⌊r/2⌋, \\ 0, & otherwise. \end{cases}

Let T_{1} and T_{2} be two trees with n vertices such that T_{2} covers T_{1} in GTS_{n}. By Lemma 11,

|c_{f_{λ},r}^{L_{T_{1}}^{q}}(q)| − |c_{f_{λ},r}^{L_{T_{2}}^{q}}(q)| ∈ ℝ^{+}[q^{2}] completing the proof. □

Thus, for all λ ⊢ n when 0 ≤ r ≤ n, by Theorem 1, Theorem 20 and Corollary 12, we get that the coefficient of x^{r} in d_{γ}(xI − L_{T}^{q}) decreases as we move up along GTS_{n} in absolute value for each γ ∈ {m_{λ}, s_{λ}, p_{λ}, h_{λ}, e_{λ}, f_{λ}}. Plugging in q = 1, we get the following corollary of Theorem 1, Theorem 20 and Corollary 12.

Corollary 21. For all λ ⊢ n and for all γ ∈ {m_{λ}, s_{λ}, p_{λ}, h_{λ}, e_{λ}, f_{λ}}, moving up on GTS_{n} decreases the coefficient of x^{r} in d_{γ}(xI − L_{T}) in absolute value, for 0 ≤ r ≤ n. Here L_{T} is the usual combinatorial Laplacian of the tree T.

Acknowledgement

The first author would like to acknowledge SERB, Government of India for providing a national postdoctoral fellowship with the file number PDF/2018/000828. The second author acknowledges support from project MTR/2018/000453 given by SERB, Government of India.

Our main theorem in this work was in its conjecture form, tested using the computer package “SageMath”. We thank the authors for generously releasing SageMath as an open-source package.

References

[1] Bapat, R. B., Lal, A. K., and Pati, S. A q-analogue of the distance matrix of a tree. Linear Algebra and its Applications 416 (2006), 799–814. (p. 3)

[2] Bass, H. The Ihara-Selberg zeta function of a tree lattice. International Journal of Mathematics 3 (1992), 717– 797. (p. 3)

[3] Chan, O., and Lam, T. K. Binomial Coefficients and characters of the symmetric group. Technical Report 693 (1996), National University of Singapore. (p. 3)

[4] Chan, O., and Lam, T. K. Hook immanantal inequalities for trees explained. Linear Algebra and its Applications 273 (1998), 119–131. (p. 3)

[5] Csikvári, P. On a poset of trees. Combinatorica 30 (2) (2010), 125–137. (p. 2)

[6] Eğecioğlu, Ö., and Remmel, J. B. The monomial symmetric functions and the Frobenius map. Journal of Combinatorial Theory, Series A 54, 2 (1990), 272–295. (pp. 6, 8)

[7] Foata, D., and Zeilberger, D. Combinatorial proofs of Bass’s evaluations of the Ihara–Selberg zeta function of a graph. Transactions of the American Mathematical Society 351 (1999), 2257–2274. (p. 3)

[8] Godsil, C., and Royle, G. Algebraic Graph Theory. Springer Verlag, 2001. (p. 3)

[9] Mendes, A., and Remmel, J. B. Counting with Symmetric Functions. Developments in Mathematics. Springer, Cham, 2015. (pp. 1, 6)

[10] Nagar, M. K. Eigenvalue monotonicity of q-Laplacians of trees along a poset. Linear Algebra and its Applications 571 (2019), 110–131. (p. 3)

[11] Nagar, M. K., and Sivasubramanian, S. Hook immanantal and Hadamard inequalities for q-Laplacians of trees. Linear Algebra and its Applications 523 (2017), 131–151. (pp. 3, 4)

[12] Nagar, M. K., and Sivasubramanian, S. Laplacian immanantal polynomials and the GTS poset on trees. Linear Algebra and its Applications 561 (2019), 1–23. (pp. 2, 4, 6)

[13] Schur, I. Über endliche Gruppen und Hermitesche Formen. Mathematische Zeitschrift 1 (1918), 184–207. (p. 3)

[14] Stanley, R. P. Enumerative Combinatorics, vol. 2. Cambridge University Press, 2001. (pp. 1, 2, 5)

Department of Mathematics and Statistics Indian Institute of Technology Kanpur Kanpur 208 016, India

Email address: mukesh.kr.nagar@gmail.com

Department of Mathematics Indian Institute of Technology Bombay Mumbai 400 076, India

Email address: krishnan@math.iitb.ac.in