Hook immanantal inequalities for trees explained

Abstract

Let d̄k denote the normalized hook immanant corresponding to the partition (k, 1n-k) of n. P. Heyfron proved the family of immanantal inequalities det A = d̄1(A) ≤ d̄2(A) ≤ ⋯ ≤ d̄n(A) = per A (1) for all positive semidefinite Hermitian matrices A. Motivated by a conjecture of R. Merris, it was shown by the authors that (1) may be improved to d̄k-1(L(.T)) ≤ k - 2 / k - 1d̄k(L(T)) (2) for all 2 ≤ k ≤ n whenever L(T) is the Laplacian matrix of a tree T. The proof of (2) relied on rather involved recursive relations for weighted matchings in the tree T as well as identities of hook characters. In this work, we circumvent this tedium with a new proof using the notion of vertex orientations. This approach makes (2) immediately apparent and more importantly provides an insight into why it holds, namely the absence of certain vertex orientations for all trees. As a by-product we obtain an improved bound, 0 ≤ 1 / k-1[d̄k(L(T)) - d̄k(L(S(n)))] ≤ k - 2 / k - 1d̄k(L(T)) - d̄k - 1(L(T)), where S(n) is the star with n vertices. The ease with which the inequality in (2) and its improvement are derived points to the value of the concept of vertex orientation in the study of immanantal inequalities on graphs. © 1998 Elsevier Science Inc.