Hook immanantal inequalities for Laplacians of trees

Abstract

For an irreducible character χλ of the symmetric group Sn, indexed by the partition λ, the immanant function dλ, acting on an n × n matrix A = (aij), is defined as dλ(A) = ∑σ ∈ Sn χλ(σ)Πn i = 1_ aiσ(i). The associated normalized immanant d̄λ is defined as d̄λ = dλ/χλ(identity) where identity is the identity permutation. P. Heyfron has shown that for the partitions (k, 1n - k), the normalized immanant d̄k satisfies det A = d̄1(A) ≤ d̄2(A) ≤ ⋯ ≤ d̄n(A) = per A (1) for all positive semidefinite Hermitian matrices A. When A is restricted to the Laplacian matrices of graphs, improvements on the inequalities above may be expected. Indeed, in a recent survey paper, R. Merris conjectured that d̄n - 1(A) ≤ n - 2/n - 1 d̄n(A) (2) whenever A is the Laplacian matrix of a tree. In this note, we establish a refinement for the family of inequalities in (1) when A is the Laplacian matrix of a tree, that includes (2) as a special case. These inequalities are sharp and equality holds if and only if A is the Laplacian matrix of the star. This is proved via the inequalities d̄k(A) - d̄k - 1(A) ≤ d̄k + 1(A) - d̄k(A) for k = 2,3, . . ., n - 1, where A is the Laplacian matrix of a tree. © Elsevier Science Inc., 1997.