1.1 Motivations

The original motivation for our paper came from the study of distance matrices $D_G$ of graphs G – on both the algebraic and spectral sides:

• • On the algebraic side, Graham and Pollak [Reference Graham and Pollak21] initiated the study of $D_G$ by proving: if $T_k$ is a tree on k nodes, then $\det D_{T_k}$ is independent of the tree structure and depends only on k. By now, many variants of such results are proved, for trees as well as several other families of graphs, including with q-analogs, weightings, and combinations of both of these. (See, e.g., [Reference Choudhury and Khare16] and its references for a list of such papers, results, and their common unification.)

• • Following the above work [Reference Graham and Pollak21], Graham also worked on the spectral side, and with Lovász, studied in [Reference Graham and Lovász20] the distance matrix of a tree, including computing its inverse and characteristic polynomial. This has since led to the intensive study of the roots, i.e., the “distance spectrum,” for trees and other graphs. See, e.g., the survey [Reference Aouchiche and Hansen3] for more on distance spectra.

A well-studied problem in spectral graph theory involves understanding which graphs are distance co-spectral – i.e., for which graphs $H' \not \cong K'$ , if any, do $D_{H'}, D_{K'}$ have the same spectra. Many such examples exist; see, e.g., the references in [Reference Drury and Lin18]. In particular, the characteristic polynomial of $D_G$ does not “detect” the graph G. It is thus natural to seek some other byproduct of $D_G$ which does – i.e., which recovers G up to isometry. In this paper, we find such a (to the best of our knowledge) novel graph invariant: a multivariate polynomial, which we call the blowup-polynomial of G, and which does detect G. Remarkably, this polynomial turns out to have several additional attractive properties:

• • It is multi-affine in its arguments.

• • It is also real-stable, so that its “support” yields a hitherto unexplored delta-matroid.

• • The blowup-polynomial simultaneously encodes the determinants of all graph-blowups of G (defined presently), thereby connecting with the algebraic side (see the next paragraph).

• • Its “univariate specialization” is a transformation of the characteristic polynomial of $D_G$ , thereby connecting with the spectral side as well.

Thus, the blowup-polynomial that we introduce, connects distance spectra for graphs – and more generally, for finite metric spaces – to other well-studied objects, including real-stable/Lorentzian polynomials and delta-matroids.

On the algebraic side, a natural question involves asking if there are graph families $\{ G_i : i \in I \}$ (like trees on k vertices) for which the scalars $\det (D_{G_i})$ behave “nicely” as a function of $i \in I$ . As stated above, the family of blowups of a fixed graph G (which help answer the preceding “spectral” question) not only answer this question positively as well, but the nature of the answer – multi-affine polynomiality – is desirable in conjunction with its real-stability. In fact, we will obtain many of these results, both spectral and algebraic, in greater generality: for arbitrary finite metric spaces.

The key construction required for all of these contributions is that of a blowup, and we begin by defining it more generally, for arbitrary metric spaces that are discrete (i.e., every point is isolated).

Definition 1.1 Given a metric space $(X,d)$ with all isolated points, and a function $\mathbf {n} : X \to \mathbb {Z}_{>0}$ , the $\mathbf {n}$ -blowup of X is the metric space $X[\mathbf {n}]$ obtained by creating $n_x := \mathbf {n}(x)$ copies of each point x (also termed blowups of x). Define the distance between copies of distinct points $x \neq y$ in X to still be $d(x,y)$ , and between distinct copies of the same point to be $2 d(x,X \setminus \{x\}) = 2 \inf _{y \in X \setminus \{ x \}} d(x,y)$ .

Also define the distance matrix $D_X$ and the modified distance matrix $\mathcal {D}_X$ of X via:

(1.1) $$ \begin{align} D_X := (d(x,y))_{x,y \in X}, \qquad \mathcal{D}_X := D_X + \operatorname{\mathrm{diag}}(2 d(x, X \setminus \{ x \}))_{x \in X}. \end{align} $$

Notice, for completeness, that the above construction applied to a non-discrete metric space does not yield a metric; and that blowups of X are “compatible” with isometries of X (see (1.3)). We also remark that this notion of blowup seems to be relatively less studied in the literature, and differs from several other variants in the literature – for metric spaces, e.g., [Reference Cheeger, Kleiner and Schioppa14] or for graphs, e.g., [Reference Liu29]. However, the variant studied in this paper was previously studied for the special case of unweighted graphs, see, e.g,. [Reference Hatami, Hirst and Norine24–Reference Komlós, Sárközy and Szemerédi26] in extremal and probabilistic graph theory.

1.2 Defining the blowup-polynomial; Euclidean embeddings

We now describe some of the results in this work, beginning with metric embeddings. Recall that the complete information about a (finite) metric space is encoded into its distance matrix $D_X$ (or equivalently, in the off-diagonal part of $\mathcal {D}_X$ ). Metric spaces are useful in many sub-disciplines of the mathematical sciences, and have been studied for over a century. For instance, a well-studied question in metric geometry involves understanding metric embeddings. In 1910, Fréchet showed [Reference Fréchet19] that every finite metric space with $k+1$ points isometrically embeds into $\mathbb R^k$ with the supnorm. Similarly, a celebrated 1935 theorem of Schoenberg [Reference Schoenberg37] (following Menger’s works [Reference Menger32, Reference Menger33]) says the following.

Theorem 1.2 (Schoenberg [Reference Schoenberg37])

A finite metric space $X = \{ x_0, \dots , x_k \}$ isometrically embeds inside Euclidean space $(\mathbb R^r, \| \cdot \|_2)$ if and only if its modified Cayley–Menger matrix

(1.2) $$ \begin{align} (d(x_0,x_i)^2 + d(x_0,x_j)^2 - d(x_i,x_j)^2)_{i,j=1}^k \end{align} $$

is positive semidefinite, with rank at most r.

As an aside, the determinant of this matrix is related to the volume of a polytope with vertices $x_i$ (beginning with classical work of Cayley [Reference Cayley13]), and the Cayley–Menger matrix itself connects to the principle of trilateration/triangulation that underlies the GPS system.

Returning to the present work, our goal is to study the distance matrix of a finite metric space vis-a-vis its blowups. We begin with a “negative” result from metric geometry. Note that every blowup of a finite metric space embeds into $\mathbb R^k$ (for some k) equipped with the supnorm, by Fréchet’s aforementioned result. In contrast, we employ Schoenberg’s Theorem 1.2 to show that the same is far from true when considering the Euclidean metric. Namely, given a finite metric space X, we characterize all blowups $X[\mathbf {n}]$ that embed in some Euclidean space $(\mathbb R^k, \| \cdot \|_2)$ . Since X embeds into $X[\mathbf {n}]$ , a necessary condition is that X itself should be Euclidean. With this in mind, we have the following.

Given the preceding result, we turn away from metric geometry, and instead focus on studying the family of blowups $X[\mathbf {n}]$ – through their distance matrices $D_{X[\mathbf {n}]}$ (which contain all of the information on $X[\mathbf {n}]$ ). Drawing inspiration from Graham and Pollak [Reference Graham and Pollak21], we focus on one of the simplest invariants of this family of matrices: their determinants, and the (possibly algebraic) nature of the dependence of $\det D_{X[\mathbf {n}]}$ on $\mathbf {n}$ . In this paper, we show that the function $: \mathbf {n} \mapsto \det D_{X[\mathbf {n}]}$ possesses several attractive properties. First, $\det D_{X[\mathbf {n}]}$ is a polynomial function in the sizes $n_x$ of the blowup, up to an exponential factor.

Theorem B Given $(X,d)$ a finite metric space, and a tuple of positive integers $\mathbf {n} := (n_x)_{x \in X} \in \mathbb {Z}_{>0}^X$ , the function $\mathbf {n} \mapsto \det D_{X[\mathbf {n}]}$ is a multi-affine polynomial $p_X(\mathbf {n})$ in the $n_x$ (i.e., its monomials are squarefree in the $n_x$ ), times the exponential function

$$\begin{align*}\prod_{x \in X} (-2 \; d(x, X \setminus \{ x \}))^{n_x-1}. \end{align*}$$

Moreover, the polynomial $p_X(\mathbf {n})$ has constant term $p_X(\mathbf {0}) = \prod _{x \in X} (-2 \; d(x, X \setminus \{ x \}))$ , and linear term $-p_X(\mathbf {0}) \sum _{x \in X} n_x$ .

Theorem B follows from a stronger one proved below. See Theorem 2.3, which shows, in particular, that not only do the conclusions of Theorem B hold over an arbitrary commutative ring, but moreover, the blowup-polynomial $p_X(\mathbf {n})$ is a polynomial function in the variables $\mathbf {n} = \{ n_x : x \in X \}$ as well as the entries of the “original” distance matrix $D_X$ – and moreover, it is squarefree/multi-affine in all of these arguments (where we treat all entries of $D_X$ to be “independent” variables).

We also refine the final assertions of Theorem B, by isolating in Proposition 2.6, the coefficient of every monomial in $p_X(\mathbf {n})$ . That proposition moreover provides a sufficient condition under which the coefficients of two monomials in $p_X(\mathbf {n})$ are equal.

Theorem B leads us to introduce the following notion, for an arbitrary finite metric space (e.g., every finite, connected, $\mathbb {R}_{>0}$ -weighted graph).

Remark 1.4 Definition 1.3 requires a small clarification. The polynomial map (by Theorem B)

$$\begin{align*}\mathbf{n} \mapsto \det D_{X[\mathbf{n}]} \cdot \prod_{x \in X} (-2 d(x, X \setminus \{ x \}))^{1 - n_x}, \qquad \mathbf{n} \in \mathbb{Z}_{>0}^k \end{align*}$$

can be extended from the Zariski dense subset $\mathbb {Z}_{>0}^k$ to all of $\mathbb R^k$ . (Zariski density is explained during the proof of Theorem B.) Since $\mathbb R$ is an infinite field, this polynomial map on $\mathbb R^k$ may now be identified with a polynomial, which is precisely $p_X(-)$ , a polynomial in $|X|$ variables (which we will denote by $\{ n_x : x \in X \}$ throughout the paper, via a mild abuse of notation). Now setting all arguments to be the same indeterminate yields the univariate blowup-polynomial of $(X,d)$ .

1.3 Real-stability

We next discuss the blowup-polynomial $p_X(\cdot )$ and its univariate specialization $u_X(\cdot )$ from the viewpoint of root-location properties. As we will see, the polynomial $u_X(n) = p_X(n,n,\dots ,n)$ always turns out to be real-rooted in n. In fact, even more is true. Recall that in recent times, the notion of real-rootedness has been studied in a much more powerful avatar: real-stability. Our next result strengthens the real-rootedness of $u_X(\cdot )$ to the second attractive property of $p_X(\cdot )$ – namely, real-stability.

Recall that real-stable polynomials are simply ones with real coefficients, which do not vanish when all arguments are constrained to lie in the (open) upper half-plane $\Im (z)> 0$ . Such polynomials have been intensively studied in recent years, with a vast number of applications. For instance, they were famously used in celebrated works of Borcea–Brändén (e.g., [Reference Borcea and Brändén5–Reference Borcea and Brändén7]) and Marcus–Spielman–Srivastava [Reference Marcus, Spielman and Srivastava30, Reference Marcus, Spielman and Srivastava31] to prove longstanding conjectures (including of Kadison–Singer, Johnson, Bilu–Linial, Lubotzky, and others), construct expander graphs, and vastly extend the Laguerre–Pólya–Schur program [Reference Laguerre27, Reference Pólya34, Reference Pólya and Schur35] from the turn of the 20th century (among other applications).

Theorem C reveals that for all finite metric spaces – in particular, for all finite connected graphs – the blowup-polynomial is indeed multi-affine and real-stable. The class of multi-affine real-stable polynomials has been characterized in [Reference Brändén11, Theorem 5.6] and [Reference Wagner and Wei43, Theorem 3]. (For a connection to matroids, see [Reference Brändén11, Reference Choe, Oxley, Sokal and Wagner15].) To the best of our knowledge, blowup-polynomials $p_X(\mathbf {n})$ provide novel examples/realizations of multi-affine real-stable polynomials.

1.4 Graph metric spaces: symmetries, complete multipartite graphs

We now turn from the metric-geometric Theorem A, the algebraic Theorem B, and the analysis-themed Theorem C, to a more combinatorial theme, by restricting from metric spaces to graphs. Here, we present two “main theorems” and one proposition.

1.4.1 Graph invariants and symmetries

Having shown that $\det D_{X[\mathbf {n}]}$ is a polynomial in $\mathbf {n}$ (times an exponential factor), and that $p_X(\cdot )$ is always real-stable, our next result explains a third attractive property of $p_X(\cdot )$ : The blowup-polynomial of a graph $X = G$ is indeed a (novel) graph invariant. To formally state this result, we begin by re-examining the blowup-construction for graphs and their distance matrices.

A distinguished sub-class of discrete metric spaces is that of finite simple connected unweighted graphs G (so, without parallel/multiple edges or self-loops). Here, the distance between two nodes $v,w$ is defined to be the (edge-)length of any shortest path joining $v,w$ . In this paper, we term such objects graph metric spaces. Note that the blowup $G[\mathbf {n}]$ is a priori only defined as a metric space; we now adjust the definition to make it a graph.

Definition 1.5 Given a graph metric space $G = (V,E)$ , and a tuple $\mathbf {n} = (n_v : v \in V)$ , the $\mathbf {n}$ -blowup of G is defined to be the graph $G[\mathbf {n}]$ – with $n_v$ copies of each vertex v – such that a copy of v and one of w are adjacent in $G[\mathbf {n}]$ if and only if $v \neq w$ are adjacent in G.

(For example, the $\mathbf {n}$ -blowup of a complete graph is a complete multipartite graph.) Now note that if G is a graph metric space, then so is $G[\mathbf {n}]$ for all tuples $\mathbf {n} \in \mathbb {Z}_{>0}^{|V|}$ . The results stated above thus apply to every such graph G – more precisely, to the distance matrices of the blowups of G.

To motivate our next result, now specifically for graph metric spaces, we first relate the symmetries of the graph with those of its blowup-polynomial $p_G(\mathbf {n})$ . Suppose a graph metric space $G = (V,E)$ has a structural (i.e., adjacency-preserving) symmetry $\Psi : V \to V$ – i.e., an (auto-)isometry as a metric space. Denoting the corresponding relabeled graph metric space by $\Psi (G)$ ,

(1.3) $$ \begin{align} D_G = D_{\Psi(G)}, \qquad \mathcal{D}_G = \mathcal{D}_{\Psi(G)}, \qquad p_G(\mathbf{n}) \equiv p_{\Psi(G)}(\mathbf{n}). \end{align} $$

It is thus natural to ask if the converse holds – i.e., if $p_G(\cdot )$ helps recover the group of auto-isometries of G. A stronger result would be if $p_G$ recovers G itself (up to isometry). We show that both of these hold.

Theorem D Given a graph metric space $G = (V,E)$ and a bijection $\Psi : V \to V$ , the symmetries of the polynomial $p_G$ equal the isometries of G. In particular, any (equivalently all) of the statements in (1.3) hold, if and only if $\Psi $ is an isometry of G. More strongly, the polynomial $p_G(\mathbf {n})$ recovers the graph metric space G (up to isometry). However, this does not hold for the polynomial $u_G$ .

As the proof reveals, one in fact needs only the homogeneous quadratic part of $p_G$ , i.e., its Hessian matrix $((\partial _{n_v} \partial _{n_{v'}} p_G)(\mathbf {0}_V))_{v,v' \in V}$ , to recover the graph and its isometries. Moreover, this associates to every graph a partially symmetric polynomial, whose symmetries are precisely the graph-isometries.

Our next result works more generally in metric spaces X, hence is stated over them. Note that the polynomial $p_X(\mathbf {n})$ is “partially symmetric,” depending on the symmetries (or isometries) of the distance matrix (or metric space). Indeed, partial symmetry is as much as one can hope for, because it turns out that “full” symmetry (in all variables $n_x$ ) occurs precisely in one situation.

Proposition 1.6 Given a finite metric space X, the following are equivalent:

1. (1) The polynomial $p_X(\mathbf {n})$ is symmetric in the variables $\{ n_x, \ x \in X \}$ .

2. (2) The metric $d_X$ is a rescaled discrete metric: $d_X(x,y) = c \mathbf {1}_{x \neq y}\ \forall x,y \in X$ , for some $c>0$ .

1.4.2 Complete multipartite graphs: novel characterization via stability

The remainder of this section returns back to graphs. We next present an interesting byproduct of the above results: a novel characterization of the class of complete multipartite graphs. Begin by observing from the proof of Theorem C that the polynomials $p_G(\cdot )$ are stable because of a determinantal representation (followed by inversion). However, they do not enjoy two related properties:

1. (1) $p_G(\cdot )$ is not homogeneous.

2. (2) The coefficients of the multi-affine polynomial $p_G(\cdot )$ are not all of the same sign; in particular, they cannot form a probability distribution on the subsets of $\{ 1, \dots , k \}$ (corresponding to the various monomials in $p_G(\cdot )$ ). In fact, even the constant and linear terms have opposite signs, by the final assertion in Theorem B.

These two (unavailable) properties of real-stable polynomials are indeed important and well-studied in the literature. Corresponding to the preceding numbering:

1. (1) Very recently, Brändén and Huh [Reference Brändén and Huh12] introduced and studied a distinguished class of homogeneous real polynomials, which they termed Lorentzian polynomials (defined below). Relatedly, Gurvits [Reference Gurvits, Kotsireas and Zima23] / Anari–Oveis Gharan–Vinzant [Reference Anari, Oveis Gharan and Vinzant2] defined strongly/completely log-concave polynomials, also defined below. These classes of polynomials have several interesting properties as well as applications (see, e.g., [Reference Anari, Oveis Gharan and Vinzant1, Reference Anari, Oveis Gharan and Vinzant2, Reference Brändén and Huh12, Reference Gurvits, Kotsireas and Zima23] and related/follow-up works).

2. (2) Recall that strongly Rayleigh measures are probability measures on the power set of $\{ 1, \dots , k \}$ whose generating (multi-affine) polynomials are real-stable. These were introduced and studied by Borcea, Brändén, and Liggett in the fundamental work [Reference Borcea, Brändén and Liggett8]. This work developed the theory of negative association/dependence for such measures, and enabled the authors to prove several conjectures of Liggett, Pemantle, and Wagner, among other achievements.

Given that $p_G(\cdot )$ is always real-stable, a natural question is if one can characterize those graphs for which a certain homogenization of $p_G(\cdot )$ is Lorentzian, or a suitable normalization is strongly Rayleigh. The standard mathematical way to address obstacle (1) above is to “projectivize” using a new variable $z_0$ , while for obstacle (2) we evaluate at $(-z_1, \dots , -z_k)$ , where we use $z_j$ instead of $n_{x_j}$ to denote complex variables. Thus, our next result proceeds via homogenization at $-z_0$ .

Theorem E Say $G = (V,E)$ with $|V|=k$ . Define the homogenized blowup-polynomial

(1.4) $$ \begin{align} \widetilde{p}_G(z_0, z_1, \dots, z_k) := (-z_0)^k p_G \left( \frac{z_1}{-z_0}, \dots, \frac{z_k}{-z_0} \right) \in \mathbb{R}[z_0, z_1, \dots, z_k]. \end{align} $$

Then the following are equivalent:

1. (1) The polynomial $\widetilde {p}_G(z_0, z_1, \dots , z_k)$ is real-stable.

2. (2) The polynomial $\widetilde {p}_G(\cdot )$ has all coefficients (of the monomials $z_0^{k - |J|} \prod _{j \in J} z_j$ ) nonnegative.

3. (3) We have $(-1)^k p_G(-1,\dots ,-1)> 0$ , and the normalized “reflected” polynomial

   $$\begin{align*}(z_1, \dots, z_k) \quad \mapsto \quad \frac{p_G(-z_1, \dots, -z_k)}{p_G(-1,\dots,-1)} \end{align*}$$
   is strongly Rayleigh. In other words, this (multi-affine) polynomial is real-stable and has nonnegative coefficients (of all monomials $\prod _{j \in J} z_j$ ), which sum up to $1$ .

4. (4) The modified distance matrix $\mathcal {D}_G$ (see Definition 1.1) is positive semidefinite.

5. (5) G is a complete multipartite graph.

Theorem E is a novel characterization result of complete multipartite graphs in the literature, in terms of real stability and the strong(ly) Rayleigh property. Moreover, given the remarks preceding Theorem E, we present three further equivalences to these characterizations.

Corollary 1.7 Definitions in Section 4.2. The assertions in Theorem E are further equivalent to:

1. (6) The polynomial $\widetilde {p}_G(z_0, \dots , z_k)$ is Lorentzian.

2. (7) The polynomial $\widetilde {p}_G(z_0, \dots , z_k)$ is strongly log-concave.

3. (8) The polynomial $\widetilde {p}_G(z_0, \dots , z_k)$ is completely log-concave.

We quickly explain the corollary. Theorem E(1) implies $\widetilde {p}_G$ is Lorentzian (see [Reference Brändén and Huh12, Reference Choe, Oxley, Sokal and Wagner15]), which implies Theorem E(2). The other equivalences follow from [Reference Brändén and Huh12, Theorem 2.30], which shows that – for any real homogeneous polynomial – assertions (7), (8) here are equivalent to $\widetilde {p}_G$ being Lorentzian.

Remark 1.8 As we see in the proof of Theorem E, when $\mathcal {D}_G$ is positive semidefinite, the homogeneous polynomial $\widetilde {p}_G(z_0, \dots , z_k)$ has a determinantal representation, i.e.,

$$\begin{align*}\widetilde{p}_G(z_0, \dots, z_k) = c \cdot \det( z_0 \operatorname{\mathrm{Id}}_k + \sum_{j=1}^k z_j A_j), \end{align*}$$

with all $A_j$ positive semidefinite and $c \in \mathbb R$ . In Proposition A.2, we further compute the mixed characteristic polynomial of these matrices $A_j$ (see (A.1) for the definition), and show that up to a scalar, it equals the “inversion” of the univariate blowup-polynomial, i.e., $z_0^k u_G(z_0^{-1})$ .

Remark 1.9 We also show that the univariate polynomial $u_G(x)$ is intimately related to the characteristic polynomial of $D_G$ (i.e., the “distance spectrum” of G), whose study was one of our original motivations. See Proposition 4.2 and the subsequent discussion, for precise statements.

1.5 Two novel delta-matroids

We conclude with a related byproduct: two novel constructions of delta-matroids, one for every finite metric space and the other for each tree graph. Recall that a delta-matroid consists of a finite “ground set” E and a nonempty collection of feasible subsets $\mathcal {F} \subseteq 2^E$ , satisfying $\bigcup _{F \in \mathcal {F}} F = E$ as well as the symmetric exchange axiom: Given $A,B \in \mathcal {F}$ and $x \in A \Delta B$ (their symmetric difference), there exists $y \in A \Delta B$ such that $A \Delta \{ x, y \} \in \mathcal {F}$ . Delta-matroids were introduced by Bouchet in [Reference Bouchet9] as a generalization of the notion of matroids.

Each (skew-)symmetric matrix $A_{k \times k}$ over a field yields a linear delta-matroid $\mathcal {M}_A$ as follows. Given any matrix $A_{k \times k}$ , let $E := \{ 1, \dots , k \}$ and let a subset $F \subseteq E$ belong to $\mathcal {M}_A$ if either F is empty or the principal submatrix $A_{F \times F}$ is nonsingular. In [Reference Bouchet10], Bouchet showed that if A is (skew-)symmetric, then the set system $\mathcal {M}_A$ is indeed a delta-matroid, which is said to be linear.

We now return to the blowup-polynomial. First, recall a 2007 result of Brändén [Reference Brändén11]: given a multi-affine real-stable polynomial, the set of monomials with nonzero coefficients forms a delta-matroid. Thus, from $p_X(\mathbf {n}),$ we obtain a delta-matroid, which as we will explain is linear.

The blowup delta-matroid $\mathcal {M}_{\mathcal {D}_X}$ is – even for X a finite connected unweighted graph – a novel construction that arises out of metric geometry rather than combinatorics, and one that seems to be unexplored in the literature (and unknown to experts). Of course, it is a simple, direct consequence of Brändén’s result in [Reference Brändén11]. However, the next delta-matroid is less direct to show.

We further prove, this notion of (in)feasible subsets in $\mathcal {M}'(T)$ does not generalize to all graphs. Thus, $\mathcal {M}'(T)$ is a combinatorial (not matrix-theoretic) delta-matroid that is also unstudied in the literature to the best of our knowledge, and which arises from every tree, but interestingly, not from all graphs.

As a closing statement here: in addition to further exploring the real-stable polynomials $p_G(\mathbf {n})$ , it would be interesting to obtain connections between these delta-matroids $\mathcal {M}_{\mathcal {D}_G}$ and $\mathcal {M}'(T)$ , and others known in the literature from combinatorics, polynomial geometry, and algebra.

1.6 Organization of the paper

The remainder of the paper is devoted to proving the above Theorems A through F; this will require developing several preliminaries along the way. The paper is clustered by theme; thus, the next two sections and the final one respectively involve, primarily:

• • (commutative) algebraic methods – to prove the polynomiality of $p_X(\cdot )$ (Theorem B), and to characterize those X for which it is a symmetric polynomial (Proposition 1.6);

• • methods from real-stability and analysis – to show $p_X(\cdot )$ is real-stable (Theorem C);

• • metric geometry – to characterize for a given Euclidean finite metric space X, all blowups that remain Euclidean (Theorem A), and to write down a related “tropical” version of Schoenberg’s Euclidean embedding theorem from [Reference Schoenberg37].

In the remaining Section 4, we prove Theorems D–F. In greater detail: we focus on the special case of $X = G$ a finite simple connected unweighted graph, with the minimum edge-distance metric. After equating the isometries of G with the symmetries of $p_G(\mathbf {n})$ , and recovering G from $p_G(\mathbf {n})$ , we prove the aforementioned characterization of complete multipartite graphs G in terms of $\widetilde {p}_G$ being real-stable, or $p_G(-\mathbf {n}) / p_G(-1, \dots , -1)$ being strongly Rayleigh. Next, we discuss a family of blowup-polynomials from this viewpoint of “partial” symmetry. We also connect $u_G(x)$ to the characteristic polynomial of $D_G$ , hence to the distance spectrum of G. Finally, we introduce the delta-matroid $\mathcal {M}'(T)$ for every tree, and explore its relation to the blowup delta-matroid $\mathcal {M}_{\mathcal {D}_T}$ (for T a path), as well as extensions to general graphs. We end with Appendices A and B that contain supplementary details and results.

We conclude this section on a philosophical note. Our approach in this work adheres to the maxim that the multivariate polynomial is a natural, general, and more powerful object than its univariate specialization. This is of course famously manifested in the recent explosion of activity in the geometry of polynomials, via the study of real-stable polynomials by Borcea–Brändén and other researchers; but also shows up in several other settings – we refer the reader to the survey [Reference Sokal and Webb40] by Sokal for additional instances. (E.g., a specific occurrence is in the extreme simplicity of the proof of the multivariate Brown–Colbourn conjecture [Reference Royle and Sokal36, Reference Sokal39], as opposed to the involved proof in the univariate case [Reference Wagner42].)

4.1 Connections to the distance spectrum; $p_G$ recovers G

We begin with an observation (for completeness), which ties into one of our original motivations by connecting the blowup-polynomial $u_G$ to the distance spectrum of G, i.e., to the eigenvalues of the distance matrix $D_G$ . The study of these eigenvalues began with the work of Graham and Lovász [Reference Graham and Lovász20], and by now, is a well-developed program in the literature (see, e.g., [Reference Aouchiche and Hansen3]). Our observation here is the following.

Alternately, $\lambda \neq -2$ is an eigenvalue of $D_G$ if and only if $\frac {2}{2 + \lambda }$ is a root of $u_G$ .

Proof First, note from the definitions that $u_G(0) = \det (-2 \operatorname {\mathrm {Id}}_V) \neq 0$ . We now compute

$$\begin{align*}u_G(n) = \det (-2 \operatorname{\mathrm{Id}}_V + n (2 \operatorname{\mathrm{Id}}_V + D_G)) = (2n)^{|V|} \det( \operatorname{\mathrm{Id}}_V + \textstyle{\frac{1}{2}} D_G - n^{-1} \operatorname{\mathrm{Id}}_V). \end{align*}$$

Thus, n is a (nonzero) root of $u_G$ if and only if $n^{-1}$ is an eigenvalue of $\operatorname {\mathrm {Id}}_V + \frac {1}{2} D_G$ . The result follows from here.

In the distance spectrum literature, much work has gone into studying the largest eigenvalue of $D_G$ , called the “distance spectral radius” in the literature, as well as the smallest eigenvalue of $D_G$ . An immediate application of Proposition 4.2 provides an interpretation of another such eigenvalue.

We refer the reader to further discussions about $\alpha _{\max }(u_G)$ in and around Proposition A.4.

Following these observations that reinforce our motivating connections between distance spectra and the blowup-polynomial, we now move on to the proof of Theorem D. Recall, this result shows that (the homogeneous quadratic part of) $p_G$ recovers/detects the graph and its isometries – but $u_G$ does not do so.

Proof of Theorem D

We prove the various assertions in serial order. One implication for the first assertion was described just above the theorem-statement. Conversely, suppose $p_G(\mathbf {n}) \equiv p_{\Psi (G)}(\mathbf {n})$ . Fix vertices $v \neq w \in V$ , and equate the coefficient of $n_v n_w$ on both sides using Proposition 2.6:

$$\begin{align*}(-2)^{|V|-2} \det \begin{pmatrix} 2 & d(v,w) \\ d(v,w) & 2 \end{pmatrix} = (-2)^{|V|-2} \det \begin{pmatrix} 2 & d(\Psi(v),\Psi(w)) \\ d(\Psi(v),\Psi(w)) & 2 \end{pmatrix},\\[-6pt] \end{align*}$$

since $d_G(v, V \setminus \{ v \}) = 1\ \forall v \in V$ . Thus $d(\Psi (v), \Psi (w)) = d(v,w)$ for all $v, w \in V$ , so $\Psi $ is an isometry.

The second assertion is shown as follows. By Proposition 2.6, the vertex set can be obtained from the nonzero monomials $n_v n_w$ (since every edge yields a nonzero monomial). In particular, $|V|$ is recovered. Again by Proposition 2.6, there is a bijection between the set of edges $v \sim w$ in G and the monomials $n_v n_w$ in $p_G(\mathbf {n})$ with coefficient $3(-2)^{|V|-2}$ . Thus, all quadratic monomials in $p_G(\mathbf {n})$ with this coefficient reveal the edge set of G as well.

Finally, to show that $u_G$ does not detect the graph G, consider the two graphs $H,K$ in Figure 1.

Figure 1:

Two non-isometric graphs on six vertices with co-spectral blowups.

Both graphs have vertex sets $\{ 1, \dots , 6 \}$ , and are not isomorphic. Now define (see Remark 4.4):

$$\begin{align*}H' := H[(2,1,1,2,1,1)], \qquad K' := K[(2,1,1,1,1,2)]. \end{align*}$$

Then $H', K'$ are not isometric, but a direct computation reveals:

$$\begin{align*}u_{H'}(n) = u_{K'}(n) = -320 n^6 + 3,712 n^5 - 10,816 n^4 + 10,880 n^3 - 1,664 n^2 - 2,048 n + 256.\end{align*}$$

Remark 4.5 As the proof of Theorem D reveals, for any graph metric space $G = (V,E)$ , the Hessian of the blowup-polynomial carries the same information as the matrix $\mathcal {D}_G \in \mathbb {Z}_{>0}^{V \times V}$ :

(4.3) $$ \begin{align} \mathcal{H}(p_G) := ((\partial_{n_v} \partial_{n_{v'}} p_G)(\mathbf{ 0}))_{v,v' \in V} = (-2)^{|V|} \mathbf{1}_{|V| \times |V|} - (-2)^{|V|-2} \mathcal{D}_G^{\circ 2}, \end{align} $$

where $\mathcal {D}_G^{\circ 2}$ is the entrywise square of the modified distance matrix $\mathcal {D}_G$ .

4.2 Complete multipartite graphs via real-stability

The next result we show is Theorem E (described in the title of this subsection). Before doing so, we define the three classes of polynomials alluded to in Corollary 1.7, as promised there (and for the self-sufficiency of this paper).

1. (1) Brändén–Huh [Reference Brändén and Huh12] defined a polynomial $p \in \mathbb R[x_1, \dots , x_k]$ to be Lorentzian if $p(\cdot )$ is homogeneous of some degree d, has nonnegative coefficients, and given any indices $0 \leqslant j_1, \dots , j_{d-2} \leqslant k$ , if

   $$\begin{align*}g(x_1, \dots, x_k) := \left( \partial_{x_{j_1}} \ldots \partial_{x_{j_{d-2}} } p \right)(x_1, \dots, x_k), \end{align*}$$
   then the Hessian matrix $\mathcal {H}_g := (\partial _{x_i} \partial _{x_j} g)_{i,j=1}^k \in \mathbb R^{k \times k}$ is Lorentzian. (This last term means that $\mathcal {H}_g$ is nonsingular and has exactly one positive eigenvalue.)

2. (2) Suppose $p \in \mathbb R[x_1, \dots , x_k]$ has nonnegative coefficients. Gurvits [Reference Gurvits, Kotsireas and Zima23] defined p to be strongly log-concave if for all $\alpha \in \mathbb {Z}_{\geqslant 0}^k$ , either the derivative $\displaystyle \partial ^\alpha (p) := \prod _{i=1}^k \partial _{x_i}^{\alpha _i} \cdot p$ is identically zero, or $\log (\partial ^\alpha (p))$ is defined and concave on $(0,\infty )^k$ .

3. (3) Suppose $p \in \mathbb R[x_1, \dots , x_k]$ has nonnegative coefficients. Anari, Oveis Gharan, and Vinzant [Reference Anari, Oveis Gharan and Vinzant2] defined p to be completely log-concave if for all integers $m \geqslant 1$ and matrices $A = (a_{ij}) \in [0,\infty )^{m \times k}$ , either the derivative $\displaystyle \partial _A (p) := \prod _{i=1}^m \left ( \sum _{j=1}^k a_{ij} \partial _{x_j} \right ) \cdot p$ is identically zero, or $\log (\partial _A (p))$ is defined and concave on $(0,\infty )^k$ .

Having written these definitions, we proceed to the main proof.

Proof of Theorem E

We prove the cyclic chain of implications:

$$\begin{align*}(4) \ \implies \ (1) \ \implies \ \{ (1), (2) \} \ \implies \ (3) \ \implies \ (2) \ \implies \ (4) \ \Longleftrightarrow \ (5). \end{align*}$$

We begin with a short proof of $(1) \implies (2)$ via Lorentzian polynomials from Corollary 1.7. It was shown in [Reference Brändén and Huh12, pp. 828–829] that if $(1)$ holds then $\widetilde {p}_G$ is Lorentzian (see also [Reference Choe, Oxley, Sokal and Wagner15, Theorem 6.1]), and in turn, this implies $(2)$ by definition (or by loc. cit.).

We next show that $(3) \implies (2)$ . Observe that

(4.4) $$ \begin{align} \frac{p_G(-z_1, \dots, -z_k) \cdot (-1)^k}{p_G(-1, \dots, -1) \cdot (-1)^k} \equiv \frac{\widetilde{p}_G(1, z_1, \dots, z_k)}{\widetilde{p}_G(1,1,\dots,1)}. \end{align} $$

Now if $(3)$ holds, then $\widetilde {p}_G(1,1,\dots ,1) = (-1)^k p_G(-1, \dots , -1)> 0$ , so the polynomial

$$\begin{align*}(-1)^k p_G(-z_1, \dots, -z_k) = \widetilde{p}_G(1,z_1, \dots, z_k) \end{align*}$$

has all coefficients nonnegative, using $(3)$ and (4.4). Since $p_G(\cdot )$ is multi-affine (or by inspecting the form of $\widetilde {p}_G(\cdot )$ ), this shows $(3) \implies (2)$ . Now to show $\{ (1), (2) \} \implies (3)$ , note that the sum of all coefficients in $\widetilde {p}_G(\cdot )$ equals

$$\begin{align*}\widetilde{p}_G(1,1,\dots,1) = (-1)^k p_G(-1,\dots,-1), \end{align*}$$

and by $(2)$ , this dominates the “constant term” of $p_G$ , i.e.,

$$ \begin{align*} (-1)^k p_G(-1,\dots,-1) \geqslant \widetilde{p}_G(1,0,\dots,0) = &\ (-1)^k p_G(0,\dots,0)\\ = &\ (-1)^k \prod_{v \in V} (-2 d(v, V \setminus \{ v \}))> 0. \end{align*} $$

In particular, $(-1)^k p_G(-1,\dots ,-1)> 0$ , proving a part of $(3)$ . Hence using $(2)$ and (4.4), all coefficients of the “reflected” polynomial are nonnegative; and the normalization shows that the coefficients sum to $1$ . It remains to show that the “reflected” polynomial $p_G(-\mathbf {z}) / p_G(-1,\dots ,-1)$ is real-stable. Once again, using (4.4) and that $(-1)^k p_G(-1,\dots ,-1)> 0$ , it suffices to show that $\widetilde {p}_G(1,z_1, \dots , z_k)$ is real-stable. But this follows from $(1)$ by specializing to $z_0 \mapsto 1 \in \mathbb R$ . This finally shows that $(1)$ and $(2)$ together imply $(3)$ .

We next show the equivalence of $(4)$ and $(5)$ . If $G = K_k$ , then $\mathcal {D}_G = \operatorname {\mathrm {Id}}_k + \mathbf {1}_{k \times k}$ is positive semidefinite. Hence so is $\mathcal {D}_{K_k[\mathbf {n}]}$ for all $\mathbf {n}$ , by Lemma 3.2(4). The converse follows from [Reference Lin, Hong, Wang and Shu28, Theorem 1.1], since $\mathcal {D}_G = D_G + 2 \operatorname {\mathrm {Id}}_{|V(G)|}$ .

Finally, we will show $(2) \implies (4) \implies (1)$ . First, assume (2) $\widetilde {p}_G(\cdot )$ has nonnegative coefficients. Fix a subset $J \subseteq \{ 1, \dots , k \}$ ; using Proposition 2.6(1), the coefficient of $z_0^{k - |J|} \prod _{j \in J} z_j$ equals

$$\begin{align*}(-1)^{k - |J|} \cdot \det (\mathcal{D}_G)_{J \times J} \prod_{j \in \{ 1, \dots, k \} \setminus J} (-d_{jj}) = \det (\mathcal{D}_G)_{J \times J} \prod_{j \in \{ 1, \dots, k \} \setminus J} 2 d_G(v_j, V \setminus \{ v_j \}). \end{align*}$$

By the hypotheses, this expression is nonnegative for every $J \subseteq \{ 1, \dots , k \}$ . Hence, $\mathcal {D}_G$ has all principal minors nonnegative (and is symmetric), so is positive semidefinite, proving (4).

Finally, if (4) $\mathcal {D}_G$ is positive semidefinite, then so is $\mathcal {C}_G$ . As above, write $\mathcal {C}_G = (-\Delta _{\mathbf {a}_G})^{-1/2} \mathcal {D}_G (-\Delta _{\mathbf {a}_G})^{-1/2}$ , and compute using that $-\Delta _{\mathbf {a}_G}$ is a positive definite diagonal matrix:

(4.5) $$ \begin{align} \widetilde{p}_G(z_0, z_1, \dots, z_k) = &\ \det(z_0 \cdot (-\Delta_{\mathbf{a}_G}) + \Delta_{\mathbf{z}} \mathcal{D}_G)\notag\\ = &\ \det (-\Delta_{\mathbf{a}_G})^{1/2} \det (z_0 \operatorname{\mathrm{Id}}_k + \Delta_{\mathbf{z}} \mathcal{C}_G) \det (-\Delta_{\mathbf{a}_G})^{1/2}\notag\\ = &\ \det (-\Delta_{\mathbf{a}_G}) \det (z_0 \operatorname{\mathrm{Id}}_k + \Delta_{\mathbf{z}} \mathcal{C}_G). \end{align} $$

(As an aside, the second factor in the final expression was termed as the multivariate characteristic polynomial of $\mathcal {C}_G$ , in [Reference Brändén and Huh12, Section 4.4].)

Now $\mathcal {C}_G$ has a positive semidefinite square root $\sqrt {\mathcal {C}_G}$ by the hypotheses. We claim that

$$\begin{align*}\det (z_0 \operatorname{\mathrm{Id}}_k + \Delta_{\mathbf{z}} \sqrt{\mathcal{C}_G} \sqrt{\mathcal{C}_G}) = \det (z_0 \operatorname{\mathrm{Id}}_k + \sqrt{\mathcal{C}_G} \Delta_{\mathbf{z}} \sqrt{\mathcal{C}_G}); \end{align*}$$

this follows by expanding the determinant of $\begin {pmatrix} z_0 \operatorname {\mathrm {Id}}_k & -\sqrt {\mathcal {C}_G} \\ \Delta _{\mathbf {z}} \sqrt {\mathcal {C}_G} & \operatorname {\mathrm {Id}}_k \end {pmatrix}$ in two different ways, both using Schur complements. Therefore – and as in the proof of Theorem C – we have

(4.6) $$ \begin{align} \begin{aligned} \widetilde{p}_G(z_0, z_1, \dots, z_k) = &\ \det (-\Delta_{\mathbf{a}_G}) \det (z_0 \operatorname{\mathrm{Id}}_k + \sqrt{\mathcal{C}_G} \Delta_{\mathbf{z}} \sqrt{\mathcal{C}_G})\\ = &\ \det (-\Delta_{\mathbf{a}_G}) \det \left( z_0 \operatorname{\mathrm{Id}}_k + \sum_{j=1}^k z_j \sqrt{\mathcal{C}_G} E_{jj} \sqrt{\mathcal{C}_G} \right). \end{aligned} \end{align} $$

Now the coefficient of each $z_j, \ j \geqslant 0$ inside the above determinant is a positive semidefinite matrix. It follows by [Reference Borcea and Brändén5, Proposition 2.4] (see the text around (3.5)) that $\widetilde {p}_G(\cdot )$ is real-stable, proving (1).

This proves the equivalence. The final assertion is immediate from (4) via Lemma 3.2(4).

4.3 Symmetries; monomials with zero coefficients

The results in this paper are developed with the goal of being used in proving the main theorems in the opening section. The only exceptions are one of the appendices (below), and this present subsection, in which our goal is to provide further intuition for blowup-polynomials of graph metric spaces G. To do so, we study a concrete family of graph metric spaces $K^{(l)}_k$ – for which we compute the blowup-polynomials and reveal connections to symmetric functions. In addition, these computations lead to the study of certain monomials whose coefficients in $p_G$ vanish – this provides intuition for proving Theorem F.

We begin from the proof of Theorem D, which shows that the blowup-polynomial of G is a partially symmetric polynomial, in the sense of being invariant under the subgroup $\mathrm {Isom}(G)$ (of isometries of G) of $S_{V(G)}$ (the permutations of $V(G)$ ). For instance, $p_G(\mathbf {n})$ is symmetric in $\mathbf {n}$ for G a complete graph; whereas $p_G$ possesses “cyclic” symmetries for G a cycle; and so on.

In addition to these global symmetries (i.e., isometries) of G, there also exist “local symmetries.” For example, suppose $G = P_k$ is a path graph, with vertex $x_i$ adjacent to $x_{i \pm 1}$ for $1 < i < k$ . For any $1 < i \leqslant j < k$ , the coefficient of the monomials

$$\begin{align*}n_{x_{i-1}} n_{x_i} \ldots n_{x_j} \qquad \text{and} \qquad n_{x_i} n_{x_{i+1}} \ldots n_{x_{j+1}} \end{align*}$$

are equal, by Proposition 2.6(3). A similar result holds more generally for banded graphs with bandwidth $d \geqslant 1$ , in which a vertex $x_i$ is adjacent to $x_j$ if and only if $0 < |i-j| < d$ and $1 \leqslant i,j \leqslant k$ .

Example 4.8 We now use this principle of symmetry to compute the blowup-polynomial for a two-parameter family of graph metric spaces

$$\begin{align*}G = K_k^{(l)}, \qquad 0 \leqslant l \leqslant k-2. \end{align*}$$

(This will shortly be followed by another application: a sufficient condition for when certain monomials do not occur in $p_G(\mathbf {n})$ .) Here, $K_k^{(l)}$ denotes the complete graph $K_k$ from which the edges $(1,2), \dots , (1,l+1)$ have been removed. This leads to three types of vertices:

$$\begin{align*}\{ 1 \}, \qquad \{ 2, \dots, l+1 \}, \qquad \{ l+2, \dots, k \}, \end{align*}$$

and correspondingly, the isometry group $\mathrm {Isom}(K_k^{(l)}) \cong S_l \times S_{k-l-1}$ . Notice that the vertices $2, \dots , k$ form a complete induced subgraph of $K_k^{(l)}$ .

The graphs $K_k^{(l)}$ are all chordal (i.e., do not contain an induced m-cycle for any $m \geqslant 4$ ), and include as special cases: complete graphs (for $l=0$ ) as well as complete graphs with one pendant vertex (for $l=k-2$ ). The “almost complete graph” $K_k^{(1)}$ (missing exactly one edge) is another special case, important from the viewpoint of matrix positivity: it was crucially used in [Reference Guillot, Khare and Rajaratnam22] to compute a graph invariant which arose out of analysis and positivity, for every chordal graph. This was termed the critical exponent of a graph in [Reference Guillot, Khare and Rajaratnam22], and seems to be a novel graph invariant.

By the remarks above, the blowup-polynomial in the $n_{v_i}$ (which we will replace by $n_i,\ 1 \leqslant i \leqslant k$ for convenience) will be symmetric separately in $\{ n_2, \dots , n_{l+1} \}$ and in $\{ n_{l+2}, \dots , n_k \}$ . In particular, since the polynomial is multi-affine in the $n_i$ , the only terms that appear will be of the form

(4.7) $$ \begin{align} n_1^{\varepsilon_1} e_r(n_2, \dots, n_{l+1}) e_s(n_{l+2}, \dots, n_k), \end{align} $$

where $\varepsilon _1 = 0$ or $1$ , and $e_r(\cdot )$ is the elementary symmetric (homogeneous, multi-affine, and, in fact, real-stable) polynomial for every $r \geqslant 0$ (with $e_0(\cdot ) := 1$ ).

With this preparation, we can state and prove the following result for the graphs $K_k^{(l)}$ .

Proposition 4.9 Fix nonnegative integers $k,l$ such that $0 \leqslant l \leqslant k-2$ . With $K_k^{(l)}$ as defined above, and denoting $n_{v_i}$ by $n_i$ for convenience (with $1 \leqslant i \leqslant k$ ), we have

$$ \begin{align*} p_{K_k^{(l)}}(\mathbf{n}) = &\ \sum_{r=0}^l \sum_{s=0}^{k-l-1} \left[ (-2)^{k-r-s} (1 + r + s) \right] e_r(n_2, \dots, n_{l+1}) e_s(n_{l+2}, \dots, n_k)\\ &\ + n_1 \sum_{r=0}^l \sum_{s=0}^{k-l-1} \left[ (-2)^{k-r-s-1} (1 -r) (s+2) \right] e_r(n_2, \dots, n_{l+1}) e_s(n_{l+2}, \dots, n_k). \end{align*} $$

Notice that setting $n_1=0$ , we obtain the blowup-polynomial of the complete graph $K_{k-1}$ , in the variables $n_2, \dots , n_k$ . This clearly equals (via $r+s \leadsto s$ ):

$$\begin{align*}\sum_{s=0}^{k-1} (-2)^{k-s} (1+s) e_s(n_2, \dots, n_k), \end{align*}$$

and it also equals the expression in (2.4) (modulo relabeling of the variables) since the underlying metric spaces are isometric. A similar computation holds upon working with $l=0$ .

Proof of Proposition 4.9

We begin by exploiting the symmetries in $K_k^{(l)}$ , which imply that given a subset $I \subseteq \{ 1, \dots , k \}$ , the coefficient of $\prod _{i \in I} n_i$ depends only on the three integers

$$\begin{align*}\varepsilon_1 := \mathbf{1}(1 \in I), \qquad r := \# (I \cap \{ 2, \dots, l+1 \}), \qquad s := \# (I \cap \{ l+2, \dots, k \}). \end{align*}$$

Now using (4.7), it follows that the blowup-polynomial indeed has the desired form:

$$ \begin{align*} p_{K_k^{(l)}}(\mathbf{n}) = &\ \sum_{r=0}^l \sum_{s=0}^{k-l-1} a_{0,r,s} e_r(n_2, \dots, n_{l+1}) e_s(n_{l+2}, \dots, n_k)\\ &\ + n_1 \sum_{r=0}^l \sum_{s=0}^{k-l-1} a_{1,r,s} e_r(n_2, \dots, n_{l+1}) e_s(n_{l+2}, \dots, n_k), \end{align*} $$

for some coefficients $a_{\varepsilon _1,r,s} \in \mathbb R$ . It remains to compute these coefficients, and we begin with the coefficients $a_{0,r,s}$ . By a computation akin to the proof of Proposition 2.6(1), these are obtained by specializing $n_1 = 0$ , which leads to a power of $(-2)$ times a principal minor of $\mathcal {D}_{K_k^{(l)}}$ not involving its first row or column. But this is the determinant of a principal submatrix of

$$\begin{align*}\operatorname{\mathrm{Id}}_{k-1} + \mathbf{1}_{(k-1) \times (k-1)} \end{align*}$$

of size $(r+s) \times (r+s)$ , and so a direct computation implies the desired formula:

$$\begin{align*}a_{0,r,s} = (-2) \cdot (-2)^{k-r-s-1} \cdot (1 + r + s). \end{align*}$$

It remains to compute $a_{1,r,s}$ , which equals $(-2)^{k-r-s-1}$ times the determinant of the block matrix

$$\begin{align*}\mathcal{D}_{r,s} := \begin{pmatrix} 2 & 2 \mathbf{1}_{r \times 1}^T & \mathbf{1}_{s \times 1}^T \\ 2 \mathbf{1}_{r \times 1} & \operatorname{\mathrm{Id}}_r + \mathbf{1}_{r \times r} & \mathbf{1}_{r \times s} \\ \mathbf{1}_{s \times 1} & \mathbf{1}_{s \times r} & \operatorname{\mathrm{Id}}_s + \mathbf{1}_{s \times s} \end{pmatrix} = \begin{pmatrix} 2 & v^T \\ v & C_{r,s} \end{pmatrix} \in \mathbb R^{(1+r+s) \times (1+r+s)}, \end{align*}$$

where $v := (2 \mathbf {1}_{r \times 1}^T \quad \mathbf {1}_{s \times 1}^T)^T \in \mathbb R^{r+s}$ , and $C_{r,s} = \operatorname {\mathrm {Id}}_{r+s} + \mathbf {1}_{(r+s) \times (r+s)}$ denotes the principal submatrix of $\mathcal {D}_{r,s}$ obtained by removing its first row and column. Now $C_{r,s}^{-1} = \operatorname {\mathrm {Id}} - (1+r+s)^{-1} \mathbf {1}_{(r+s) \times (r+s)}$ , so using Schur complements,

$$ \begin{align*} &\ \det \mathcal{D}_{r,s}\\ = &\ \det C_{r,s} \cdot \det \left( 2 - v^T C_{r,s}^{-1} v \right)\\ = &\ 2(1+r+s) - \begin{pmatrix} 2 \mathbf{1}_{r \times 1} \\ \mathbf{1}_{s \times 1} \end{pmatrix}^T \begin{pmatrix} (1+r+s) \operatorname{\mathrm{Id}}_r - \mathbf{1}_{r \times r} & - \mathbf{1}_{r \times s} \\ - \mathbf{1}_{s \times r} & (1+r+s) \operatorname{\mathrm{Id}}_s - \mathbf{1}_{s \times s} \end{pmatrix} \begin{pmatrix} 2 \mathbf{1}_{r \times 1} \\ \mathbf{1}_{s \times 1} \end{pmatrix}, \end{align*} $$

and a straightforward (if careful) calculation reveals this quantity to equal $(1-r)(s+2)$ .

Example 4.10 As an additional example, we compute the blowup-polynomial for several other graphs at once. The path graph $P_3$ is a special case of the star graphs $K_{1,k-1}$ , and in turn, these as well as the cycle graph $C_4$ are special cases of complete bipartite graphs $K_{r,s}$ . As $K_{r,s} = K_2[(r,s)]$ is a blowup, we can use Lemma 3.2(2) and equation (2.4) for $k=2$ , to obtain

(4.8) $$ \begin{align} \begin{aligned} &\ p_{K_{r,s}}(n_1, \dots, n_r; m_1, \dots, m_s)\\ = &\ (-2)^{r+s-2} \left( 3 \sum_{i=1}^r n_i \cdot \sum_{j=1}^s m_j - 4 \sum_{i=1}^r n_i - 4 \sum_{j=1}^s m_j + 4 \right). \end{aligned} \end{align} $$

As one observes by visual inspection, the coefficient in Proposition 4.9 of $n_1 n_2$ times any monomial in the (“type- $3$ ”) node-variables $n_{l+2}, \dots , n_k$ , vanishes. Similarly, in (4.8), there are many coefficients that vanish – in fact, every coefficient of total degree at least $3$ . These facts can be explained more simply, by the following result about zero terms in the blowup-polynomial.

For example, for H the path graph $P_4$ with vertices $a - b - c - d$ , the coefficients of $n_a n_c, n_a n_b n_c$ , and $n_b n_d, n_b n_c n_d$ in $p_H(\mathbf {n})$ are all zero, since the path subgraphs $a-b-c$ and $b-c-d$ are both isomorphic to the graph blowup $K_2[(1,2)]$ .

This result also extends to arbitrary finite metric spaces.

4.4 The tree-blowup delta-matroid

We conclude this section by proving Theorem F about the delta-matroid $\mathcal {M}'(T)$ for every tree, which seems to be unstudied in the literature. We then explore (a) if this delta-matroid equals the blowup delta-matroid $\mathcal {M}_{\mathcal {D}_T}$ ; and (b) if this construction can be extended to arbitrary graphs.

To motivate the construction of $\mathcal {M}'(T)$ , which we term the tree-blowup delta-matroid, we begin by applying Proposition 4.11 with $G = P_2 = K_2$ and $G[\mathbf {n}] = P_3$ . An immediate consequence is the following.

In light of this, we take a closer look at $\mathcal {D}_X$ for $X = P_k$ a path graph. Given an integer $k \geqslant 1$ , the path graph $P_k$ has vertex set $\{ 1, \dots , k \}$ , with vertices $i,j$ adjacent if and only if $|i-j|=1$ .

Recall from [Reference Bouchet10] that the set system $\mathcal {M}_{\mathcal {D}_X}$ (defined a few lines before Corollary 1.10) is a linear delta-matroid for every finite metric space – in particular, for every graph metric space, such as $P_k$ . It turns out (by inspection) that Corollary 4.12 describes all of the principal minors of $\mathcal {D}_{P_k}$ which vanish – i.e., the complement of the delta-matroid $\mathcal {M}_{\mathcal {D}_{P_k}}$ in the power-set of $\{ 1, \dots , k \}$ – for small values of k. While this may or may not hold for general k, the same construction still defines a delta-matroid, and one that is hitherto unexplored as well.

Proposition 4.13 Given an integer $k \geqslant 3$ , define the set system

$$\begin{align*}\mathcal{B}(P_k) := 2^{\{ 1, \dots, k \}} \setminus \left\{ \ \{ i, i+1, i+2 \}, \ \ \{ i, i+2 \} \ : \ 1 \leqslant i \leqslant k-2 \right\}. \end{align*}$$

Then $\mathcal {B}(P_k)$ is a delta-matroid.

We now strengthen this result to the case of arbitrary trees (for completeness, recall that a tree is a finite connected graph without a cycle $C_n$ for $n \geqslant 3$ ). We begin with a few basic observations on trees, which help in the next proofs. Every pair of vertices in T is connected by a unique path in T. Moreover, every connected sub-graph of T is a tree, and every (nonempty) set I of vertices of T is contained in a unique smallest sub-tree $T(I)$ , called its Steiner tree. We also recall that a leaf, or a pendant vertex, is any vertex with degree one, i.e., adjacent to exactly one vertex.

With this terminology at hand, Theorem F asserts that the feasible subsets of V form a delta-matroid. Note, if $T = P_k$ is a path graph, then $\mathcal {M}'(T)$ equals the delta-matroid $\mathcal {B}(P_k)$ above.

The proof of Theorem F requires a preliminary result, which characterizes when a graph G is a nontrivial blowup, and which then connects this to the distance spectrum of G.

Specializing Proposition 4.15 to trees, we obtain the following.

As mentioned above, the delta-matroids $\mathcal {M}_{\mathcal {D}_{P_k}} = \mathcal {M}'(P_k) = \mathcal {B}(P_k)$ for small values of k. It is natural to seek to know if this result holds for all path graphs, and perhaps even more generally. It turns out that this is false, and the situation is more involved even for path graphs $P_k$ with $k \geqslant 9$ .

Proof An explicit (and longwinded) inspection shows that $\mathcal {M}_{\mathcal {D}_{P_k}} = \mathcal {B}(P_k)$ for $3 \leqslant k \leqslant 8$ . Another direct computation shows that $\det \mathcal {D}_{P_9} = 0$ . Hence, by Proposition 2.6(2), the coefficient of $n_1 n_2 \ldots n_9$ in $p_{P_k}(\mathbf {n})$ also vanishes, for all $k \geqslant 9$ . Using Proposition 2.6(3), it follows that

$$\begin{align*}\{ i, i+1, \dots, i+8 \} \not\in \mathcal{M}_{\mathcal{D}_{P_k}}, \qquad \forall k \geqslant 9, \ 1 \leqslant i \leqslant k-8. \end{align*}$$

But these sets all lie in $\mathcal {B}(P_k)$ , so $\mathcal {B}(P_k) \supsetneq \mathcal {M}_{\mathcal {D}_{P_k}}$ for $k \geqslant 9$ .

As also promised above, we next explore the question of extending Theorem F from trees to arbitrary graphs. The key observation is that the equivalence $(1) \Longleftrightarrow (2)$ in Proposition 4.15 extends Corollary 4.16. This suggests how to define a set system in $2^{V(G)}$ for every graph metric space G, which specializes to the delta-matroid $\mathcal {M}'(T)$ when $G = T$ is a tree.

For instance, if $G = T$ is a tree, then it is not hard to see that $\mathcal {M}^{\prime }_1(T) = \mathcal {M}^{\prime }_2(T) = \mathcal {M}'(T)$ , which was studied in Theorem F. Thus, a question that is natural given that theorem, is whether or not $\mathcal {M}^{\prime }_1(G)$ and/or $\mathcal {M}^{\prime }_2(G)$ is a delta-matroid for every graph G?

This question is also natural from the viewpoint of the blowup-polynomial, in that if $I \subseteq V$ is infeasible of the second kind, then the coefficient in $p_G(\mathbf {n})$ of the monomial $\prod _{i \in I} n_i$ is zero by Proposition 4.11. Nevertheless, our next result shows that this question has a negative answer, already for a graph on seven vertices. Thus, the construction of $\mathcal {M}'(T)$ does not extend to arbitrary graph metric spaces in either of the above two ways.

Proposition 4.19 There exists a graph G such that neither $\mathcal {M}^{\prime }_1(G)$ nor $\mathcal {M}^{\prime }_2(G)$ is a delta-matroid.

Figure 2:

A graph on seven vertices.

5.1 Real-closed analogs

For completeness, we now provide analogs of some of the results proved above, over arbitrary real-closed fields. As this subsection is not used anywhere else in the paper, we will be brief, and also assume familiarity with real-closed fields; we refer the reader to the opening chapter of [Reference Bochnak, Coste and Roy4] for this.

In this part, we suppose $\mathbb K$ is a real-closed field, where we denote the nonnegative elements in $\mathbb K$ by: $r \geqslant 0$ . Also let $\overline {\mathbb K} = \mathbb K[\sqrt {-1}]$ denote an algebraic closure of $\mathbb K$ , where we fix a choice of “imaginary” square root $i = \sqrt {-1}$ in $\overline {\mathbb K}$ . Then several “real” notions can be defined over $\mathbb K, \overline {\mathbb K}$ :

1. (1) A symmetric matrix $A \in \mathbb K^{k \times k}$ is said to be positive semidefinite (resp. positive definite) if $x^T A x \geqslant 0$ (resp. $x^T A x> 0$ ) for all nonzero vectors $x \in \mathbb K^n$ .

2. (2) A matrix $A \in \mathbb K^{k \times k}$ is orthogonal if $A A^T = \operatorname {\mathrm {Id}}_k$ .

3. (3) Given $z = x + iy \in \overline {\mathbb K}$ with $x,y \in \mathbb K$ , we define $\Re (z) := x$ and $\Im (z) := y$ .

4. (4) We say that a multivariable polynomial $p \in \overline {\mathbb K}[z_1, \dots , z_k]$ is stable if $p(z_1, \dots , z_k)\ \neq 0$ whenever $\Im (z_j)> 0\ \forall j$ .

Now (an analog of) the spectral theorem holds for symmetric matrices $A = A^T \in \mathbb K^{k \times k}$ . Moreover, every such matrix A is positive semidefinite if and only if it has nonnegative eigenvalues in $\mathbb K$ – and if so, then it has a positive semidefinite square root $\sqrt {A}$ . One also has the following.

The two parts of this proposition were proved over $\mathbb K = \mathbb R$ in [Reference Borcea and Brändén5, Reference Brändén and Huh12], respectively. Thus, they hold over an arbitrary real closed field $\mathbb K$ by Tarski’s principle, since all of these notions can be expressed in the first-order language of ordered fields. Also note that the equivalence in the second part indeed makes sense over some real-closed fields, e.g., $\mathbb K = \mathbb R$ , or $\mathbb K$ the field of convergent (real) Puiseux series with rational powers, where it was proved in [Reference Brändén and Huh12, Theorem 3.19]. The notions of Lorentzian and strongly/completely log-concave polynomials over the latter field can be found in [Reference Brändén and Huh12] (see page 861).

Remark 5.2 Schoenberg’s Euclidean embeddability result (Theorem 1.2) – stated and used above – turns out to have an alternate characterization in a specific real-closed field: the convergent generalized Puiseux series $\mathbb R \{ t \}$ with real powers. Recall, the elements of $\mathbb R \{ t \}$ are series

$$\begin{align*}\sum_{n=0}^\infty c_n t^{\alpha_n}, \qquad c_0, c_1, \ldots \in \mathbb R, \end{align*}$$

satisfying: (a) the exponents $\alpha _0 < \alpha _1 < \cdots $ are real; (b) $\{ -\alpha _n : n \geqslant 0, \ c_n \neq 0 \}$ is well-ordered; and (c) $\sum _n c_n t^{\alpha _n}$ is convergent on a punctured open disk around the origin. Such a series is defined to be positive if its leading coefficient is positive. It is known (see, e.g., [Reference Speyer41, Section 1.5]) that this field is real-closed; moreover, its algebraic closure is the degree- $2$ extension $\mathbb {C} \{ t \}$ , where real coefficients in the definition above are replaced by complex ones. Now, we claim that the following holds.

We conclude this part by formulating the promised tropical version of some of our results above. As the notion of a $\mathbb K_{\geqslant 0}$ -valued metric (can be easily defined, but) is not very common in the literature, we formulate the next result in greater generality.

One can prove this result from the same result over $\mathbb K = \mathbb R$ , via Tarski’s principle. Alternately, the case of $\mathbb K = \mathbb R$ was essentially proved in Theorem E; the slightly more general versions here (for $\mathbb K = \mathbb R$ , with M instead of $\mathcal {D}_G$ ) require only minimal modifications to the earlier proofs. These proofs (for $\mathbb K = \mathbb R$ ) go through over arbitrary real-closed $\mathbb K$ with minimal further modifications, given Proposition 5.1.