Let T be a tree on n vertices and let
be the q-analogue of its Laplacian. For a partition
, let the normalized immanant of
indexed by λ be denoted as
. A string of inequalities among
is known when λ ...varies over hook partitions of n as the size of the first part of λ decreases. In this work, we show a similar sequence of inequalities when λ varies over two row partitions of n as the size of the first part of λ decreases. Our main lemma is an identity involving binomial coefficients and irreducible character values of
indexed by two row partitions. Our proof can be interpreted using the combinatorics of Riordan paths and our main lemma admits a nice probabilisitic interpretation involving peaks at odd heights in generalized Dyck paths or equivalently involving special descents in Standard Young Tableaux with two rows. As a corollary, we also get inequalities between
and
when
and
are comparable trees in the
poset and when
and
are both two rowed partitions of n, with
having a larger first part than
.
The Eulerian polynomial
AExc
n
(
t
)
enumerating excedances in the symmetric group
S
n
is known to be gamma positive for all
n
. When enumeration is done over the type B and type D Coxeter groups, ...the type B and type D Eulerian polynomials are also gamma positive for all
n
. We consider
AExc
n
+
(
t
)
and
AExc
n
-
(
t
)
, the polynomials which enumerate excedance in the alternating group
A
n
and in
S
n
-
A
n
, respectively. We show that
AExc
n
+
(
t
)
is gamma positive iff
n
≥
5
is odd. When
n
≥
4
is even,
AExc
n
+
(
t
)
is not even palindromic, but we show that it is the sum of two gamma positive summands. An identical statement is true about
AExc
n
-
(
t
)
. We extend similar results to the excedance based Eulerian polynomial when enumeration is done over the positive elements in both type B and type D Coxeter groups. Gamma positivity results are known when excedance is enumerated over derangements in
S
n
. We extend some of these to the case when enumeration is done over even and odd derangements in
S
n
.
Formulas for the determinant of distance matrix
of tree
are known in the unweighted case and in the case when the edges of
have commuting variable weights. Associated with the
(4PC) and a tree
are ...two matrices, the
and the
. These are not full rank matrices and their rank, a basis
, and formulas for the determinant when restricted to the rows and columns of
are known. In this work, we generalize both these matrices to the case when the edges of
have commuting variable weights and determine edge-weighted counterparts of known results.
Arithmetic matroids arising from a list A of integral vectors in Zn are of recent interest and the arithmetic Tutte polynomial M
(x, y) of A is a fundamental invariant with deep connections to ...several areas. In this work, we consider two lists of vectors coming from the rows of matrices associated to a tree T. Let T = (V, E) be a tree with |V| = n and let L
be the q-analogue of its Laplacian L in the variable q. Assign q = r for r ∈ ℤ with r/= 0, ±1 and treat the n rows of L
after this assignment as a list containing elements of ℤ
. We give a formula for the arithmetic Tutte polynomial M
(x, y) of this list and show that it depends only on n, r and is independent of the structure of T. An analogous result holds for another polynomial matrix associated to T: ED
, the n × n exponential distance matrix of T. More generally, we give formulae for the multivariate arithmetic Tutte polynomials associated to the list of row vectors of these two matriceswhich shows that even the multivariate arithmetic Tutte polynomial is independent of the tree T. As a corollary, we get the Ehrhart polynomials of the following zonotopes: - Z
obtained from the rows of EDT and - Z
obtained from the rows of L
. Further, we explicitly find the maximum volume ellipsoid contained in the zonotopes Z
, Z
and show that the volume of these ellipsoids are again tree independent for fixed n, q. A similar result holds for the minimum volume ellipsoid containing these zonotopes.
The 2-Steiner distance matrix of a tree Azimi, Ali; Sivasubramanian, Sivaramakrishnan
Linear algebra and its applications,
12/2022, Letnik:
655
Journal Article
Let
= (
,
) be a connected graph with 2-connected blocks
,
, . . . ,
. Motivated by the exponential distance matrix, Bapat and Sivasubramanian in 4 defined its product distance matrix
and showed that ...det
only depends on det
for 1 ≤
≤
and not on the manner in which its blocks are connected. In this work, when distances are symmetric, we generalize this result to the Smith Normal Form of
and give an explicit formula for the invariant factors of
The alternating descent statistic on permutations was introduced by Chebikin as a variant of the descent statistic. In this paper, we get a formula for the signed enumeration of alternating descents ...and in our proof we need a signed convolution type identity involving the Eulerian polynomials. When n is even, we give a more general multivariate version and we also get a formula for the signed enumeration of the alternating major index. We generalize our results to the case when alternating descents are summed up with sign over the elements in classical Weyl groups.
Reifegerste and independently, Petersen and Tenner studied a statistic \(\mathrm{drops}()\) on permutations in \(\mathfrak{S}_n\). Two other studied statistics on \(\mathfrak{S}_n\) are ...\(\mathrm{depth}\) and \(\mathrm{exc}\). Using descents in \({\it canonical\ reduced\ words}\) of elements in \(\mathfrak{S}_n\), we give an involution \(f_A: \mathfrak{S}_n \mapsto \mathfrak{S}_n\) that leads to a neat formula for the signed trivariate enumerator of \(\mathrm{drops},\mathrm{depth}, \mathrm{exc}\) in \(\mathfrak{S}_n\). This gives a simple formula for the signed univariate drops enumerator in \(\mathfrak{S}_n\). For the type-B Coxeter group \(\mathfrak{B}_n\) as well, using similar techniques, we show analogous results. For the type D Coxeter group, we again get analogous results, but our proof is inductive. Under the famous Foata-Zeilberger bijection \(\phi_{FZ}\) which takes permutations to restricted Laguerre histories, we show that permutations \(\pi\) and \(f_A(\pi)\) map to the same Motzkin path, but have different history components. Using the Foata-Zeilberger bijection, we also get a continued fraction for the generating function enumerating the pair of statistics \(\mathrm{drops}\) and \(\mathrm{MAD}\). Graham and Diaconis determined the mean and the variance of the Spearman metric of disarray \(D(\pi)\) when one samples \(\pi\) from \(\mathfrak{S}_n\) at random. As an application of our results, we get the mean and variance of the statistic \(\mathrm{drops}(\pi)\) when we sample \(\pi\) from \(\mathcal{A}_n\) at random.
Unimodality of the normalized coefficients of the characteristic polynomial of distance matrices of trees are known and bounds on the location of its peak (the largest coefficient) are also known. ...Recently, an extension of these results to distance matrices of block graphs was given. In this work, we extend these results to two additional distance-type matrices associated with trees: the Min-4PC matrix and the 2-Steiner distance matrix. We show that the sequences of coefficients of the characteristic polynomials of these matrices are both unimodal and log-concave. Moreover, we find the peak location for the coefficients of the characteristic polynomials of the Min-4PC matrix of any tree on \(n\) vertices. Further, we show that the Min-4PC matrix of any tree on \(n\) vertices is isometrically embeddable in \(\mathbb{R}^{n-1}\) equipped with the \(\ell_1\) norm.