# A Generalization of the Graham-Pollak Tree Theorem to Even-Order Steiner
Distance

Joshua Cooper and Gabrielle Tauscheck

###### Abstract

Graham and Pollak showed in 1971 that the determinant of a tree’s distance
matrix depends only on its number of vertices, and, in particular, it is
always nonzero. The Steiner distance of a collection of $k$ vertices in a
graph is the fewest number of edges in any connected subgraph containing those
vertices; for $k=2$, this reduces to the ordinary definition of graphical
distance. Here, we show that the hyperdeterminant of the $k$-th order Steiner
distance hypermatrix is always nonzero if $k$ is even, extending their result
beyond $k=2$. Previously, the authors showed that the $k$-Steiner distance
hyperdeterminant is always zero for $k$ odd, so together this provides a
generalization to all $k$. We conjecture that not just the vanishing, but the
value itself, of the $k$-Steiner distance hyperdeterminant of an $n$-vertex
tree depends only on $k$ and $n$.

##  1 Introduction

In an influential 1971 paper, Graham and Pollak ([3]) computed the determinant
of the distance matrix of a $n$-vertex tree, i.e., the $n\times n$ matrix $D$
whose $(i,j)$ entry is the shortest-path distance between $i$ and $j$.
Strikingly, the formula only depends on $n$, and nothing more about the tree:

$\det(D)=(1-n)(-2)^{n-2}.$ (1)

In particular, this quantity is nonzero for any $n\geq 1$.

Steiner distance generalizes the classical notion of distance in a graph $G$
from pairs of vertices to any subset $S\subseteq V(G)$, as the minimum number
of edges in any connected subgraph of $G$ containing $S$ (or possibly $\infty$
if there is no such subgraph). Therefore, partly inspired by recent
developments in hypermatrices, Y. Mao asks (q.v. [4]) how to generalize (1) to
hyperdeterminants of order-$k$ Steiner distances in trees. The present authors
showed previously ([1]) that, for $k$ odd (and $n\geq 3$), the Steiner
distance hyperdeterminant is $0$. In this paper, we show that the Steiner
distance is always nonzero for $k$ even (and $n\geq 2$), implying a weak
generalization of the Graham-Pollak Theorem to Steiner distance: for $n\geq
3$, whether the hyperdeterminant vanishes depends only on $k$. In fact, we
conjecture a much stronger statement: the value of the hyperdeterminant (not
just whether it vanishes) only depends on $n$ and $k$ in general. This has
been checked computationally for all trees with
$(k,n)\in\\{(4,4),(4,5),(6,4)\\}$ and holds trivially for $n=2$, $n=3$. The
following table shows the common values of the hyperdeterminant, factored into
primes.

$\begin{array}[]{l|l}(n,k)&\det(\mathcal{S})\\\
\hline\cr\hline\cr(4,2)&-2^{2}\cdot 7\\\ (4,3)&2^{12}\cdot 7\cdot 23^{4}\\\
(4,4)&-2^{38}\cdot 3^{27}\cdot 5^{6}\cdot 7\cdot 13^{12}\\\ (4,5)&2^{203}\cdot
5^{32}\cdot 7\cdot 11^{32}\cdot 23^{24}\cdot 37^{8}\\\ (6,2)&-11^{2}\cdot
31\\\ (6,3)&2^{14}\cdot 3^{16}\cdot 11^{4}\cdot 31\cdot 19231^{4}\\\
(6,4)&-2^{82}\cdot 3^{17}\cdot 11^{8}\cdot 31\cdot 41^{12}\cdot 71^{6}\cdot
89^{6}\cdot 151^{24}\cdot 257^{24}\cdot 1511^{12}\\\ (8,2)&-2^{6}\cdot
29^{2}\cdot 127\\\ (8,3)&2^{56}\cdot 13^{16}\cdot 29^{4}\cdot 113^{8}\cdot
127\cdot 1009^{8}\cdot 2143^{4}\end{array}$

First, some notation and facts about hyperdeterminants are needed. The
following theorem is a useful generalization of the fact that the matrix
determinant is the unique irreducible polynomial in the entries of $M$ whose
vanishing coincides with the existence of nontrivial solutions to the linear
system corresponding to $M$.

######  Theorem 1.1 ([2] Theorem 1.3).

The hyperdeterminant $\det(M)$ of the order-$k$, dimension-$n$ hypermatrix
$M=(M_{i_{1},\ldots,i_{k}})_{i_{1},\ldots,i_{k}=1}^{n}$ is a monic irreducible
polynomial which evaluates to zero iff there is a nonzero simultaneous
solution to $\nabla f_{M}=\vec{0}$, where

$f_{M}(x_{1},\ldots,x_{n})=\sum_{i_{1},\ldots,i_{k}}M_{i_{1},\ldots,i_{k}}\prod_{j=1}^{k}x_{i_{j}}.$

Next, we define Steiner distance.

######  Definition 1.2.

Given a graph $G$ and a subset $S$ of the vertices, the Steiner distance of
$S$, written $d_{G}(S)$ or $d_{G}(v_{1},\ldots,v_{k})$ where
$S=\\{v_{1},\ldots,v_{k}\\}$, is the number of edges in the smallest connected
subgraph of $G$ containing $S=\\{v_{1},\ldots,v_{k}\\}$. We often supress the
variable $v$ when referring to the vertices within $S$. Since such a connected
subgraph of $G$ witnessing $d_{G}(S)$ is necessarily a tree, it is called a
Steiner tree of $S$.

Then, we have a “Steiner polynomial” which reduces to the quadratic form
defined by the distance matrix for $k=2$.

######  Definition 1.3.

Given a graph $G$, the Steiner polynomial of $G$ is the $k$-form

$p^{(k)}_{G}(\mathbf{x})=\sum_{v_{1},\ldots,v_{k}\in
V(G)}d_{G}(v_{1},\ldots,v_{k})x_{1}\cdots x_{k}$

where we often suppress the subscript and/or superscript on $p^{(k)}_{G}$ if
it is clear from context.

Equivalently, we could define the Steiner polynomial to be the $k$-form
associated with the Steiner hypermatrix:

######  Definition 1.4.

Given a graph $G$, the Steiner $k$-matrix (or just “Steiner hypermatrix” if
$k$ is understood) of $G$ is the order-$k$, cubical hypermatrix
$\mathcal{S}_{G}$ of dimension $n$ whose $(v_{1},\ldots,v_{k})$ entry is
$d_{G}(v_{1},\ldots,v_{k})$.

Throughout the sequel, we write $D_{r}$ for the operator $\partial/\partial
x_{r}$, and we always assume that $T$ is a tree.

######  Definition 1.5.

Given a graph $G$ on $n$ vertices, the Steiner $k$-ideal – or just “Steiner
ideal” if $k$ is clear – of $G$ is the ideal in
$\mathbb{C}[x_{1},\ldots,x_{n}]$ generated by the polynomials
$\\{D_{j}p_{G}\\}_{j=1}^{n}$.

Thus, the Steiner ideal is the Jacobian ideal of the Steiner polynomial of
$G$. Equivalently, we could define the Steiner $k$-ideal via hypermatrices. We
use the notation $\mathcal{S}(x^{k-1},*)$ to represent
$\mathcal{S}(\overbrace{x,x,\ldots,x}^{k-1},*).$ Note that
$S(x^{k-1},*)=S(x^{k-2},*,*)x$ where $S(x^{k-2},*,*)$ is an $n\times n$ matrix
whose entries are homogeneous polynomials of degree $k-2$. Then the Steiner
$k$-ideal of a graph $G$ on $n$ vertices is the ideal in
$\mathbb{C}[x_{1},\ldots,x_{n}]$ generated by the components of
$\mathcal{S}(x^{k-1},*)$.

######  Definition 1.6.

A Steiner nullvector is a point where all the polynomials within the Steiner
ideal vanish. The set of all Steiner nullvectors – a projective variety – is
the Steiner nullvariety.

##  2 Main Results

We show that the order-$k$ Steiner distance hypermatrix of a tree $T$ on
$n+1\geq 2$ vertices has a nonzero hyperdeterminant for even $k$. Therefore,
for the remainder of this paper, we assume $T$ is a tree on at least $2$
vertices and $k$ is even. For concision, let $S=\mathcal{S}(x^{k-2},*,*)$ as
defined in the introduction, and write $S_{u}$ for the row of $S$ indexed by
$u$ and $S_{u,v}$ for the $v$ entry of $S_{u}$. We also employ multi-index
notation: for $\mathbf{i}=(i_{1},\ldots,i_{r})\in\\{0,\ldots,n\\}^{r}$ and
$\mathbf{x}=[x_{0},\ldots,x_{n}]$, write
$\mathbf{x}^{\mathbf{i}}:=\prod_{j=1}^{r}x_{i_{j}}$ and
$\nu_{t}(\mathbf{i}):=|\\{j:i_{j}=t\\}|.$

######  Proposition 2.1.

If $e=\\{u,u+1\\}$ is an edge of the tree $T$ on $n+1$ vertices
$\\{0,\ldots,n\\}$, then $S_{u}-S_{u+1}$ is a vector of the form
$\mathbf{x}=[x_{0},x_{1},\ldots,x_{n}]$ where
$x_{0}=x_{1}=\ldots=x_{u}=-\left(\sum_{i=0}^{u}x_{i}\right)^{k-2}$ and
$x_{u+1}=\ldots=x_{n}=\left(\sum_{i=u+1}^{n}x_{i}\right)^{k-2}$ with
$0,\ldots,u$ lying in one component of $T^{\prime}:=T-e$ and $u+1,\ldots,n$
lying in the other component.

###### Proof.

Note that

$S_{uw}=\sum_{\mathbf{i}\in
V(T)^{k-2}}d_{T}(u,w,\mathbf{i})\mathbf{x}^{\mathbf{i}}.$ (2)

It is sufficient to show that for any $w$ and $w^{\prime}$ that lie within the
same component of $T^{\prime}$,

$d_{T}(u,w,\mathbf{i})-d_{T}({u+1},w,\mathbf{i})=d_{T}(u,{w^{\prime}},\mathbf{i})-d_{T}({u+1},{w^{\prime}},\mathbf{i})$

holds for all $i_{1},\ldots,i_{k-2}\in V(T)$. For every case, let
$d=d_{T}(u,w,\mathbf{i})$ and $d^{\prime}=d_{T}(u,{w^{\prime}},\mathbf{i})$.

Case 1: Let $i_{1},\ldots,i_{k-2}$ lie in the same component of $T^{\prime}$
as $u$.

  1. (a)

Assume $w$ and $w^{\prime}$ also lie within the same component as $u$. Then,

$d_{T}(u,w,\mathbf{i})-d_{T}({u+1},w,\mathbf{i})=d-(d+1)=-1$
$d_{T}(u,{w^{\prime}},\mathbf{i})-d_{T}({u+1},{w^{\prime}},\mathbf{i})=d^{\prime}-(d^{\prime}+1)=-1.$

  2. (b)

Assume instead that $w$ and $w^{\prime}$ lie in the same component as $u+1$.
Then,

$d_{T}(u,w,\mathbf{i})-d_{T}(u+1,w,\mathbf{i})=d-d=0$
$d_{T}(u,w^{\prime},\mathbf{i})-d_{T}(u+1,w^{\prime},\mathbf{i})=d^{\prime}-d^{\prime}=0.$

Case 2: Let $i_{1},\ldots,i_{k-2}$ lie in the same component as $u+1$.

  1. (a)

Assume $w$ and $w^{\prime}$ also lie within the same component as $u+1$. Then,

$d_{T}(u,w,\mathbf{i})-d_{T}(u+1,w,\mathbf{i})=d-(d-1)=1$
$d_{T}(u,w^{\prime},\mathbf{i})-d_{T}(u+1,w^{\prime},\mathbf{i})=d^{\prime}-(d^{\prime}-1)=1.$

  2. (b)

Assume instead that $w$ and $w^{\prime}$ lie in the same component as $u$.
Then,

$d_{T}(u,w,\mathbf{i})-d_{T}(u+1,w,\mathbf{i})=d-d=0$
$d_{T}(u,w^{\prime},\mathbf{i})-d_{T}(u+1,w^{\prime},\mathbf{i})=d^{\prime}-d^{\prime}=0.$

Case 3: Suppose some of the vertices among $i_{1},\ldots,i_{k-2}$ lie in the
same component as $u$ and some lie in the same component as $u+1$. Then,

$d_{T}(u,w,\mathbf{i})-d_{T}(u+1,w,\mathbf{i})=d-d=0$
$d_{T}(u,w^{\prime},\mathbf{i})-d_{T}(u+1,w^{\prime},\mathbf{i})=d^{\prime}-d^{\prime}=0.$

Therefore, the vector $S_{u}-S_{u+1}$ has equal entries among the coordinates
indexed by vertices lying in the same component of $T^{\prime}$. To compute
these entries, we combine the different cases. Notice that Case 3 contributes
zero to the sum in (2); therefore, we can omit those entries in the
calculations. First, consider $x_{u}=S_{u,u}-S_{u+1,u}$. Since $u$ lies in the
same component as itself, we are working with Cases 1(a) and 2(b). Case 2(b)
contributes a zero to the summation; therefore, we need only consider the
vertices in Case 1(a), giving us
$x_{u}=-\sum_{\mathbf{i}\in\\{0,\ldots,u\\}^{k-2}}\mathbf{x}^{\mathbf{i}}=-\left(\sum_{i=0}^{u}x_{i}\right)^{k-2}$.

Now, consider $x_{u+1}=S_{u,u+1}-S_{u+1,u+1}$. Since $u+1$ lies in the same
component as itself, we are working with Cases 1(b) and 2(a). Case 1(b)
contributes a zero to the summation; therefore, we need only consider the
vertices in Case 2(a), giving us
$x_{u+1}=\sum_{\mathbf{i}\in\\{u+1,\ldots,n\\}^{k-2}}\mathbf{x}^{\mathbf{i}}=\left(\sum_{i=u+1}^{n}x_{i}\right)^{k-2}.$
∎

Let $\textbf{h}_{u}(a,b)=[h_{0},h_{1},\ldots,h_{n}]\in\mathbb{C}^{n+1}$ be a
vector with at most two distinct entries: $h_{0}=\ldots=h_{u}=a$ and
$h_{u+1}=\ldots=h_{n}=b$.

######  Proposition 2.2.

Let $\mathbf{x}=[x_{0},x_{1},\ldots,x_{n}]$ be a Steiner nullvector of a tree
$T$. All entries that correspond to leaf vertices $v$ are the same value,
equal to the summation of every entry of $\mathbf{x}$ except $x_{v}$.

###### Proof.

Since $T$ is a tree on at least $2$ vertices, it must have a leaf vertex; call
it $0$, and let $1$ be its unique neighbor. Proposition 2.1 gives $a$ and $b$
so that

$\displaystyle(D_{0}p_{T}-D_{1}p_{T})(\mathbf{x})$
$\displaystyle=\textbf{h}_{0}(a,b)^{T}\mathbf{x}$
$\displaystyle=\textbf{h}_{0}\left(-x_{0}^{k-2},\left(\sum_{i=1}^{n}x_{i}\right)^{k-2}\right)^{T}\mathbf{x}$
$\displaystyle=-x_{0}^{k-1}+\left(\sum_{i=1}^{n}x_{i}\right)^{k-1}=0$

so we may conclude that $x_{0}^{k-1}=\left(\sum_{i=1}^{n}x_{i}\right)^{k-1}$.
Since $k-1$ is odd,

$x_{0}=\sum_{i=1}^{n}x_{i}.$

From here, we see that $\sum_{i=0}^{n}x_{i}=x_{0}+x_{0}$ so that
$x_{0}=\frac{1}{2}\sum_{i=0}^{n}x_{i}$. The choice of vertex $0$ was made
arbitrarily among the leaves; therefore, every leaf corresponds to this same
entry in the nullvector, namely, $\sum_{i=1}^{n}x_{i}$. ∎

######  Proposition 2.3.

Suppose $e=\\{u,u+1\\}$ is an edge of the tree $T$ on $n+1$ vertices. Let
$0,\ldots,u$ lie in one component of $T-e$ and $u+1,\ldots,n$ lie in the other
component. Let $\mathbf{x}=[x_{0},x_{1},\ldots,x_{n}]$ be a Steiner
nullvector. Then $\sum_{i=0}^{u}x_{i}=x_{v}$ where $v$ is any leaf vertex.

###### Proof.

Proposition 2.1 gives $a$ and $b$ so that

$\displaystyle(D_{u}p_{T}-D_{u+1}p_{T})(\mathbf{x})$
$\displaystyle=\textbf{h}_{u}(a,b)^{T}\mathbf{x}$
$\displaystyle=\textbf{h}_{u}\left(-\left(\sum_{i=0}^{u}x_{i}\right)^{k-2},\left(\sum_{i=u+1}^{n}x_{i}\right)^{k-2}\right)^{T}\mathbf{x}$
$\displaystyle=-\left(\sum_{i=0}^{u}x_{i}\right)^{k-1}+\left(\sum_{i=u+1}^{n}x_{i}\right)^{k-1}=0$

so we may conclude that
$\left(\sum_{i=0}^{u}x_{i}\right)^{k-1}=\left(\sum_{i=u+1}^{n}x_{i}\right)^{k-1}$.
Since $k-1$ is odd,

$\sum_{i=0}^{u}x_{i}=\sum_{i=u+1}^{n}x_{i}.$ (3)

Assume without loss of generality that $0$ is a leaf vertex; then Proposition
2.2 gives that $x_{0}=\sum_{i=1}^{n}x_{i}$. We can rewrite (3) to be
$x_{0}+\sum_{i=1}^{u}x_{i}=x_{0}-\sum_{i=1}^{u}x_{i}$ so that

$\sum_{i=1}^{u}x_{i}=0.$

Therefore, $\sum_{i=0}^{u}x_{i}=x_{0}$ as desired. ∎

We are now in a position to describe all entries of a Steiner nullvector of a
tree $T$.

######  Proposition 2.4.

Suppose $\mathbf{x}=[x_{0},\ldots,x_{n}]$ is a Steiner nullvector of a tree
$T$ on $n+1$ vertices. Then, for each $t\in V(T)$, $x_{t}=x_{v}(2-\deg(t))$
where $v$ is any leaf vertex.

###### Proof.

First fix a leaf vertex $v$; note that Proposition 2.2 implies that $x_{v}$
does not depend on which leaf is chosen. Since $\deg(v)=1$, we have
$x_{v}=x_{v}(2-\deg(v))$.

Let $t$ be any nonleaf vertex, with degree $d>1$. Since $T$ is a tree on at
least $2$ vertices, $t$ has at least one neighbor – call it $u$ – and let $e$
be the edge $\\{t,u\\}$. Let $\mathcal{G}$ be the set of all vertices that lie
in the same component as $t$ in $T-e$. Proposition 2.3 tells us that
$\sum_{i\in\mathcal{G}}x_{i}=x_{v}$. Partition $\mathcal{G}$ into sets
$\\{t\\},\mathcal{G}_{0},\ldots,\mathcal{G}_{d-2}$ by taking $\mathcal{G}_{j}$
to be vertices of the $j$-th component induced by
$\mathcal{G}\setminus\\{t\\}$. (Note that there are only $d-1$ subsets since
the component of $T-\\{t\\}$ containing vertex $t+1$ is not included in
$\mathcal{G}$.) Once again, we can apply Proposition 2.3 to say that
$\sum_{i\in\mathcal{G}_{j}}x_{i}=x_{v}$ for $0\leq j\leq d-2$. Therefore,

$\displaystyle x_{v}$ $\displaystyle=\sum_{i\in\mathcal{G}}x_{i}$
$\displaystyle=x_{t}+\sum_{j=0}^{d-2}\sum_{i\in\mathcal{G}_{j}}x_{i}$
$\displaystyle=x_{t}+\sum_{j=0}^{d-2}x_{v}$
$\displaystyle=x_{t}+x_{v}(\deg(t)-1)$

and $x_{t}=x_{v}(2-\deg(t))$ as desired. ∎

We are now equipped to prove the main result.

######  Theorem 2.5.

For $k$ even, the Steiner $k$-matrix of a tree on at least $2$ vertices has a
nonzero hyperdeterminant.

###### Proof.

Using Proposition 2.4, we prove the result by contradiction.

Consider any tree $T$ on $n+1$ vertices where $n\geq 1$. Assume without loss
of generality that $0$ is a leaf vertex of $T$ whose neighbor is $1$. Assume
the hyperdeterminant is zero. Theorem 1.1 then implies that there exists a
nontrivial common zero of the Steiner $k$-ideal; let
$\mathbf{x}=[x_{0},x_{1},\ldots,x_{n}]$ be a Steiner nullvector of $T$. Since
the generators of the Steiner $k$-ideal are homogeneous, and $x_{0}=0$ implies
that $x_{v}=0$ for all $v$ by Proposition 2.4, we may assume $x_{0}=1$. Then,

$\displaystyle D_{1}p_{T}(\mathbf{x})$
$\displaystyle=\sum_{\mathbf{i}\in\\{0,\ldots,n\\}^{k-1}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}$
$\displaystyle=\sum_{a=0}^{k-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\\{0,\ldots,n\\}^{k-1}\\\
\nu_{0}(\mathbf{i})=a\end{subarray}}d_{T}(1,\mathbf{i},\overbrace{0,0,\ldots,0}^{a})\mathbf{x}^{\mathbf{i}}$
$\displaystyle=\sum_{a=0}^{k-1}{k-1\choose
a}x_{0}^{a}\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}}d_{T}(1,\mathbf{i},0)\mathbf{x}^{\mathbf{i}}$
$\displaystyle=\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}+\sum_{a=1}^{k-1}{k-1\choose
a}\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}}[d_{T}(1,\mathbf{i})+1]\mathbf{x}^{\mathbf{i}}$

by partitioning the vectors $\mathbf{i}$ according whether
$\nu_{0}(\mathbf{i})=0$ or $a$ for some $a>0$. Continuing to rewrite the
quantity $D_{1}p_{T}(\mathbf{x})$,

$\displaystyle=\sum_{a=0}^{k-1}{k-1\choose
a}\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}+\sum_{a=1}^{k-1}{k-1\choose
a}\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}}\mathbf{x}^{\mathbf{i}}$
$\displaystyle=\sum_{a=0}^{k-1}{k-1\choose
a}\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}+\left(1+\sum_{i=1}^{n}x_{i}\right)^{k-1}-\left(\sum_{i=1}^{n}x_{i}\right)^{k-1}$
$\displaystyle=\left(\sum_{a=0}^{k-1}{k-1\choose
a}\sum_{b=0}^{k-1-a}\sum_{\begin{subarray}{c}\mathbf{i}\in\\{1,\ldots,n\\}^{k-1-a}\\\
\nu_{1}(\mathbf{i})=b\end{subarray}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1$
$\displaystyle=\left(\sum_{a=0}^{k-1}{k-1\choose
a}\sum_{b=0}^{k-1-a}{k-1-a\choose
b}x_{1}^{b}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-a-b}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1$
$\displaystyle=\left(\sum_{a+b=0}^{k-1}{k-1\choose
a,b,k-1-a-b}x_{1}^{b}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-a-b}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1$
$\displaystyle=\left(\sum_{j=0}^{k-1}{k-1\choose j}\sum_{b=0}^{j}{j\choose
b}x_{1}^{b}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1$
$\displaystyle=\left(\sum_{j=0}^{k-1}{k-1\choose
j}\left(x_{1}+1\right)^{j}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1,$

where $j$ has been introduced to replace $a+b$. If $T$ is a tree on $2$
vertices, then $D_{1}p_{T}(\mathbf{x})=2^{k-1}-1\neq 0$. Therefore, the only
Steiner nullvector of a tree on $2$ vertices is the trivial one, and the
hyperdeterminant must be nonzero. We continue by assuming that $T$ is a tree
on at least $3$ vertices.

Upon deleting the leaf vertex $0$, we obtain a new tree $T^{\prime}$ on $n$
vertices. Let
$\mathbf{x}^{\prime}=[x_{1}^{\prime},x_{2}^{\prime},\ldots,x_{n}^{\prime}]$ be
a Steiner nullvector of $T^{\prime}$. Notice that
$\deg_{T}(1)=\deg_{T^{\prime}}(1)-1$ and
$\deg_{T}(2)=\deg_{T^{\prime}}(2),\ldots,\deg_{T}(n)=\deg_{T^{\prime}}(n).$
Using Proposition 2.4 and the definition of $\mathbf{x}$, by setting
$x^{\prime}_{v}$ = $x_{v}$ for some leaf vertex common to both $T$ and
$T^{\prime}$, we conclude that
$\mathbf{x}^{\prime}=[x_{1}+x_{0},x_{2},\ldots,x_{n}]=[x_{1}+1,x_{2},\ldots,x_{n}]$.
Then

$\displaystyle D_{1}p_{T^{\prime}}(\mathbf{x}^{\prime})$
$\displaystyle=\sum_{\mathbf{i}\in\\{1,\ldots,n\\}^{k-1}}d_{T}(1,\mathbf{i})\mathbf{x}^{\prime\mathbf{i}}$
$\displaystyle=\sum_{j=0}^{k-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\\{1,\ldots,n\\}^{k-1}\\\
\nu_{1}(\mathbf{i})=j\end{subarray}}d_{T}(1,\mathbf{i})\mathbf{x}^{\prime\mathbf{i}}$
$\displaystyle=\sum_{j=0}^{k-1}{k-1\choose
j}\left(x_{1}^{\prime}\right)^{j}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}$
$\displaystyle=\sum_{j=0}^{k-1}{k-1\choose
j}\left(x_{1}+1\right)^{j}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}.$

Since we assumed $\mathbf{x}$ and $\mathbf{x}^{\prime}$ were Steiner
nullvectors,
$D_{1}p_{T}(\mathbf{x})=0=D_{1}p_{T^{\prime}}(\mathbf{x}^{\prime})$.
Therefore,

$\displaystyle 0$
$\displaystyle=D_{1}p_{T}(\mathbf{x})-D_{1}p_{T^{\prime}}(\mathbf{x}^{\prime})$
$\displaystyle=\left(\sum_{j=0}^{k-1}{k-1\choose
j}\left(x_{1}+1\right)^{j}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}\right)+2^{k-1}-1$
$\displaystyle\quad\quad\quad-\sum_{j=0}^{k-1}{k-1\choose
j}\left(x_{1}+1\right)^{j}\sum_{\mathbf{i}\in\\{2,\ldots,n\\}^{k-1-j}}d_{T}(1,\mathbf{i})\mathbf{x}^{\mathbf{i}}$
$\displaystyle=2^{k-1}-1\neq 0.$

Therefore, the only nullvector is the trivial one, and the hyperdeterminant
must be nonzero. ∎

## References

  * [1] Joshua Cooper and Gabrielle Tauscheck.  A generalization of the Graham-Pollak tree theorem to Steiner distance.  Discrete Math., 347(4):Paper No. 113849, 7, 2024.
  * [2] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky.  Discriminants, resultants and multidimensional determinants.  Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston, MA, 2008.  Reprint of the 1994 edition.
  * [3] R. L. Graham and H. O. Pollak.  On the addressing problem for loop switching.  Bell System Tech. J., 50:2495–2519, 1971.
  * [4] Yaping Mao.  Steiner distance in graphs–A survey, 2017.


# Event anisotropy $v_{2}$ in Au+Au collisions at $\sqrt{s_{NN}}=$ 7.7 - 62.4
GeV with STAR

Shusu Shia,b (for the STAR Collaboration)  Institute of Particle Physics,
Huazhong Normal University, Wuhan, Hubei, 430079, China  Key Laboratory of
Quark and Lepton Physics (MOE) and Institute of Particle Physics, Central
China Normal University, Wuhan 430079, China

###### Abstract

We present the $v_{2}$ measurement at midrapidity from Au+Au collisions at
$\sqrt{s_{NN}}=$ 7.7, 11.5, 19.6, 27, 39 and 62.4 GeV for inclusive charged
hadrons and identified hadrons ($\pi^{\pm}$, $K^{\pm}$, $K_{S}^{0}$, $p$,
$\bar{p}$, $\phi$, $\Lambda$, $\bar{\Lambda}$, $\Xi^{-}$, $\bar{\Xi}^{+}$,
$\Omega^{-}$, $\bar{\Omega}^{+}$) up to 4 GeV/$c$ in $p_{T}$. The beam energy
and centrality dependence of charged hadron $v_{2}$ are presented with
comparison to higher energies at RHIC and LHC. The identified hadron $v_{2}$
are used to discuss the NCQ scaling for different beam energies. Significant
difference in $v_{2}(p_{T})$ is observed between particles and corresponding
anti-particles for $\sqrt{s_{NN}}<$ 39 GeV. These differences are more
pronounced for baryons compared to mesons and they increase with decreasing
energy.

††journal: Nuclear Physics A

##  1 Introduction

Searching for the phase boundary in the Quantum ChromoDynamics (QCD) phase
diagram is one of the main motivations of the Beam Energy Scan (BES) program
at RHIC. The elliptic flow ($v_{2}$) could be used as a powerful tool [1],
because of the sensitivity of underlying dynamics in the early stage of the
collisions. The Number of Constituent Quark (NCQ) scaling in the top energy
collisions at RHIC ($\sqrt{\mathrm{\it s_{NN}}}$ = 200 GeV) indicates the
collectivity has been built up in the partonic level [2, 3]. Recently, the
similar NCQ scaling of multi-strange hadrons, $\phi$ and $\Omega$, which are
less sensitive to the late hadronic interactions provides the clear evidence
of partonic collectivity [4]. An energy dependence study based on A Multi-
Phase Transport (AMPT) model indicates the NCQ scaling is related to the
degrees of freedom in the system [5]. If the partonic degree of freedom is
included in the AMPT model, the NCQ scaling (including multi-strange hadrons)
could be observed; whereas the NCQ scaling is broken in the case of including
only hadronic degree of freedom. The BES data offer us the opportunity to
investigate the QCD phase boundary with $v_{2}$ measurements. In this paper,
we present the $v_{2}$ results from the STAR experiment in Au+Au collisions at
$\sqrt{\mathrm{\it s_{NN}}}$ = 7.7 - 62.4 GeV. The particle identification for
$\pi^{\pm}$, $K^{\pm}$ and $p~{}(\overline{p})$ is achieved via the energy
loss in the Time Projection Chamber (TPC) [6] and the time of flight
information from the multi-gap resistive plate chamber detector [7]. Strange
and multi-strange hadrons are reconstructed with the decay channels:
${K}^{0}_{S}$ $\rightarrow\pi^{+}+\pi^{-}$, $\phi\rightarrow K^{+}+K^{-}$,
$\Lambda$ $\rightarrow p+\pi^{-}$
($\overline{\Lambda}\rightarrow\overline{p}+\pi^{+}$), $\Xi^{-}\rightarrow$
$\Lambda$ $+\ \pi^{-}$ ($\overline{\Xi}^{+}\rightarrow$ $\overline{\Lambda}$\+
$\pi^{+}$) and $\Omega^{-}\rightarrow$ $\Lambda$ $+\ K^{-}$
($\overline{\Omega}^{+}\rightarrow$ $\overline{\Lambda}$\+ $K^{+}$). The event
plane method [8] and cumulant method [9, 10] are used for the $v_{2}$
measurement.

##  2 Results and Discussions

Figure 1: (Color online) The top panels show $v_{2}\\{4\\}$ vs. $p_{T}$ at
midrapidity for various collision energies ($\sqrt{\mathrm{\it s_{NN}}}$ = 7.7
GeV to 2.76 TeV). The results for $\sqrt{\mathrm{\it s_{NN}}}$ = 7.7 to 200
GeV are for Au+Au collisions and those for 2.76 TeV are for Pb + Pb
collisions. The dashed red curves show the fifth order polynomial fits to the
results from Au+Au collisions at $\sqrt{\mathrm{\it s_{NN}}}$ = 200 GeV. The
bottom panels show the ratio of $v_{2}\\{4\\}$ vs. $p_{T}$ for all
$\sqrt{\mathrm{\it s_{NN}}}$ with respect to the fit curve. The results are
shown for three collision centrality classes: $10-20\%$ (a1), $20-30\%$ (b1)
and $30-40\%$ (c1) [11]. Error bars are shown only for the statistical
uncertainties respectively. Figure 2: (Color online) The difference in $v_{2}$
between particles and their corrsponding anti-particles
($v_{2}(X)-v_{2}(\bar{X})$) as a function of beam energy in Au+Au collisions
(0-80%). The statistical and systematic uncertainties are shown by vertical
line and cap respectively. The dashed lines in the plot are fits with the
equation described in the text. Figure 3: (Color online) The elliptic flow
($v_{2}$) as a function of transverse mass ($m_{T}-m_{0}$) for the selected
particles in Au+Au collisions (0-80%) at $\sqrt{\mathrm{\it s_{NN}}}$ = 7.7,
11.5, 19.6, 27, 39 and 62.4 GeV. Error bars are shown only for the statistical
uncertainties.

Figure 1 [11] shows the transverse momentrum ($p_{T}$) dependence of
$v_{2}\\{4\\}$ from $\sqrt{\mathrm{\it s_{NN}}}$ = 7.7 GeV to 2.76 TeV in
$10-20\%$ (a1), $20-30\%$ (b1) and $30-40\%$ (c1) centrality bins. The ALICE
results in Pb + Pb collisions at $\sqrt{s_{NN}}$ = 2.76 TeV are taken from
Ref. [12]. The 200 GeV data is empirically fit by a fifth order polynomial
function. For comparison, the $v_{2}$ from other energies are divided by the
fit and shown in the lower panels of Fig. 1. For $p_{T}$ below 2
$\mathrm{GeV}/c$, the $v_{2}$ values rise with increasing collision energy.
Beyond $p_{T}=2~{}\mbox{$\mathrm{GeV}/c$}$ the $v_{2}$ results show comparable
values within statistical errors. The increase of $v_{2}(p_{T})$ as a function
of energy could be due to the change of chemical composition from low to high
energies and/or larger collectivity at higher collision energy.

Figure 2 shows the $p_{T}$ independent difference in $v_{2}$ between particles
and their corresponding anti-particles. The data of collisions at
$\sqrt{\mathrm{\it s_{NN}}}$ = 19.6 and 27 GeV is new since Quark Matter 2011
[13]. The $\eta$-sub event plane method is used for the measurement. In this
method, one defines the flow vector for each particle based on particles
measured in the opposite hemisphere in pseudorapidity ($\eta$). An $\eta$ gap
of $|\eta|<0.05$ is used between negative/positive $\eta$ sub-event to reduce
the non-flow effects by enlarging the separation between the correlated
particles. $v_{2}(X)-v_{2}(\bar{X})$ ($\Delta v_{2}$) represents the average
values of the difference in $v_{2}$ between particles and corresponding anti-
particles over measured $p_{T}$ range. The dashed lines in the Fig. 2 are fits
with the function: $f_{\Delta v_{2}}(\sqrt{s_{NN}})=a\sqrt{s_{NN}}^{-b}+c$. A
monotonic increase of $\Delta v_{2}$ with decreasing collision energy is
observed and the slope of the difference increases towards lowers energies.
The difference is more pronounced for baryons compared to mesons. The observed
difference in $v_{2}$ reflects that the particles vs. anti-particles could not
fit into the NCQ scaling. The breaking of NCQ scaling between particles and
anti-particles indicates the contributions from hadronic interactions increase
in the system evolution with decreasing collision energy. The energy
dependence of $\Delta v_{2}$ could be qualitatively reproduced by the baryon
transport effect [14] or hadronic potential effect [15]. So far theoretical
calculations fail to quantitatively reproduce the measured $v_{2}$ difference
and none of the calculations could explain the correct order of particles.

Figure 3 shows the $v_{2}$ as a function of transverse mass ($m_{T}-m_{0}$)
for the selected particles for all six collision energies. In the top energy
($\sqrt{\mathrm{\it s_{NN}}}$ = 200 GeV) collisions, a clear splitting in
$v_{2}$ between baryons and mesons is observed for $m_{T}-m_{0}>1~{}{\rm
GeV}/c^{2}$. The splitting between baryons and mesons suggest the system
created in the collisions is sensitive to the quark degree of freedom. The
selected particles show a similar splitting for collision energy $\geq$ 39
GeV. The bayron and meson groups become closer to each other at all lower
energies. At $\sqrt{\mathrm{\it s_{NN}}}$ = 11.5 GeV, the splitting between
baryons and mesons is almost gone. The clear trend, a decreasing baryon-meson
splitting of $v_{2}(m_{T}-m_{0})$ beyond $m_{T}-m_{0}>1~{}{\rm GeV}/c^{2}$
indicates the hadronic interactions become more important in the lower
collision energies.

##  3 Summary

In summary, we present the $v_{2}$ measurements for charged hadrons and
identified hadrons in Au+Au collisions at $\sqrt{\mathrm{\it s_{NN}}}$ = 7.7 -
62.4 GeV. The comparison with Au+Au collisions at higher energies at RHIC
($\sqrt{\mathrm{\it s_{NN}}}$ = 62.4 and 200 GeV) and at LHC (Pb + Pb
collisions at $\sqrt{\mathrm{\it s_{NN}}}$ = 2.76 TeV) shows the
$v_{2}\\{4\\}$ values at low $p_{T}$ ($p_{T}<$ 2.0 GeV/$c$) increase with
increase in collision energy. The baryon and anti-baryon $v_{2}$ show
significant difference for $\sqrt{\mathrm{\it s_{NN}}}$ $<~{}$ 39 GeV. The
difference of $v_{2}$ between particles and corresponding anti-particles
(pions, kaons, protons, $\Lambda$s and $\Xi$s) increases with decreasing the
beam energy. The baryon-meson splitting of $v_{2}(m_{T}-m_{0})$ beyond
$m_{T}-m_{0}>1~{}{\rm GeV}/c^{2}$ becomes smaller in the lower collisions
energy and is almost gone in collisions at $\sqrt{\mathrm{\it s_{NN}}}$ = 11.5
GeV. Experimental data indicate that the hadronic interactions become more
important at the lower beam energy.

##  4 Acknowledgments

This work was supported in part by the National Natural Science Foundation of
China under grant No. 11105060, 10775060, 11135011, 11221504 and self
determined research funds of CCNU from the colleges’ basic research and
operation of MOE.

## References

  * [1] S. A. Voloshin, A. M. Poskanzer and R. Snellings, arXiv:0809.2949.
  * [2] J. Adams et al. (STAR Collaboration), Phys. Rev. Lett. 92, 052302 (2004).
  * [3] B. I. Abelev et al., (STAR Collaboration), Phys. Rev. C 81, 044902 (2010).
  * [4] S. S. Shi (for the STAR collaboration), Nucl. Phys. A 830, 187c (2009); Nucl. Phys. A 862-863, 263 (2011).
  * [5] F. Liu, K.J. Wu, and N. Xu, J. Phys. G 37 094029(2010).
  * [6] K. H. Ackermann et al. (STAR Collaboration), Nucl. Instrum. Methods A 499, 624 (2003).
  * [7] W. J. Llope (STAR TOF Group), Nucl. Instr. and Meth. B 241, 306 (2005).
  * [8] A. M. Poskanzer and S. A. Voloshin, Phys. Rev. C 58 1671 (1998).
  * [9] N. Borghini, P. M. Dinh, and J.-Y. Ollitrault, Phys. Rev. C 63, 054906 (2001).
  * [10] A. Bilandzic, R. Snellings and S.Voloshin, Phys. Rev. C 83, 044913 (2011).
  * [11] L. Adamczyk et al., (STAR Collaboration), arXiv:1206.5528.
  * [12] K. Aamodt et al. (ALICE Collaboration), Phys. Rev. Lett. 105, 252302 (2010).
  * [13] A. Schmah (for the STAR collaboration), J. Phys. G 38 124049 (2011).
  * [14] J. Dunlop, M.A. Lisa and P. Sorensen, Phys. Rev. C 84, 044914 (2011).
  * [15] J. Xu et al., Phys. Rev. C 85, 041901 (2012).