pith. sign in

arxiv: 2105.12111 · v4 · submitted 2021-05-25 · 🧮 math.MG · math.CA· math.CO

The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra

Projesh Nath Choudhury , Apoorva Khare This is my paper

Pith reviewed 2026-05-24 13:28 UTC · model grok-4.3

classification 🧮 math.MG math.CAmath.CO
keywords blowup-polynomialmetric spacereal-stable polynomialdistance matrixgraph invariantdelta-matroiddistance spectrumcomplete multipartite graph
0
0 comments X

The pith

Every finite metric space has a multi-affine real-stable blowup-polynomial recovered from the determinant of its blowup distance matrix.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper attaches to each finite metric space X a blowup-polynomial p_X in variables n_x, one per point of X. This polynomial arises by forming the blowup space X[n] with n_x copies of each point, taking the determinant of its distance matrix, and dividing out an explicit exponential factor. The resulting function of the n_x is proved to be a polynomial that is multi-affine and real-stable. When X is a connected graph G the polynomial is partially symmetric, recovers G up to isometry from its symmetries, and its univariate specialization transforms the characteristic polynomial of the distance matrix of G. The same object yields a characterization of complete multipartite graphs through a real-stability condition on a homogenization of p_G.

Core claim

To every finite metric space X we attach its blowup-polynomial p_X({n_x}), obtained from the determinant of the distance matrix of the blowup X[n] after removing an exponential factor. This p_X is a multi-affine real-stable polynomial in the n_x. When X is a connected graph G, p_G recovers G up to isometry via its symmetries, its univariate specialization u_G(x) is a transform of the characteristic polynomial of the distance matrix D_G, and complete multipartite graphs are those for which the homogenization at -1 of p_G is real-stable if and only if the normalization of p_G(-n) is strongly Rayleigh. The construction also produces a delta-matroid for each metric space and a separate one for a

What carries the argument

The blowup-polynomial p_X({n_x : x in X}), obtained as the determinant of the distance matrix of the blowup X[n] divided by an exponential factor in the n_x.

If this is right

  • p_X is multi-affine and real-stable for every finite metric space.
  • For a connected graph G, p_G together with its symmetries recovers G up to isometry.
  • The univariate specialization u_G(x) is a transform of the characteristic polynomial of the distance matrix D_G.
  • Complete multipartite graphs are characterized exactly by the real-stability of the homogenization at -1 of p_G being equivalent to strong Rayleighness of the normalization of p_G(-n).
  • Each metric space and each tree carries a novel delta-matroid derived from the blowup construction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The real-stability property may produce new combinatorial inequalities on the entries of distance matrices that are not visible from the characteristic polynomial alone.
  • One could check whether the blowup-polynomial distinguishes pairs of non-isometric metric spaces that share the same multiset of pairwise distances.
  • The tree-specific delta-matroid might admit a direct combinatorial description independent of the metric-space construction.

Load-bearing premise

The determinant of the distance matrix of the blowup X[n], after division by the explicit exponential factor, is in fact a polynomial in the n_x and satisfies the real-stability property for arbitrary metrics.

What would settle it

A finite metric space X together with explicit n_x values for which the function det(distance matrix of X[n]) divided by the exponential factor fails to be a polynomial in the n_x, or for which the resulting polynomial is not real-stable.

Figures

Figures reproduced from arXiv: 2105.12111 by Apoorva Khare, Projesh Nath Choudhury.

Figure 1
Figure 1. Figure 1: Two non-isometric graphs on six vertices with co-spectral blowups [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A graph on seven vertices definitions show that A := V and B := {v2} both lie in M′ 1 (G) ∩M′ 2 (G), and clearly, x ∈ A∆B = A \ B. Moreover, for all y ∈ V , one can verify that A∆{x, y} = A \ {x, y} (or A \ {x} if y = x) is indeed infeasible of the second kind, hence of the first. (This uses that in the induced subgraph on A \ {x, y}, either v1, v2 are both present, or w1, w2 are, and then they are copies … view at source ↗
read the original abstract

To every finite metric space $X$, including all connected unweighted graphs with the minimum edge-distance metric, we attach an invariant that we call its blowup-polynomial $p_X(\{ n_x : x \in X \})$. This is obtained from the blowup $X[{\bf n}]$ - which contains $n_x$ copies of each point $x$ - by computing the determinant of the distance matrix of $X[{\bf n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X({\bf n})$ is a polynomial, is multi-affine, and is real-stable. This naturally associates a hitherto unstudied delta-matroid to each metric space $X$; we produce another novel delta-matroid for each tree, which interestingly does not generalize to all graphs. We next specialize to the case of $X = G$ a connected unweighted graph - so $p_G$ is "partially symmetric" in $\{ n_v : v \in V(G) \}$ - and show three further results: (a) We show that the polynomial $p_G$ is indeed a graph invariant, in that $p_G$ and its symmetries recover the graph $G$ and its isometries, respectively. (b) We show that the univariate specialization $u_G(x) := p_G(x,\dots,x)$ is a transform of the characteristic polynomial of the distance matrix $D_G$; this connects the blowup-polynomial of $G$ to the well-studied "distance spectrum" of $G$. (c) We obtain a novel characterization of complete multipartite graphs, as precisely those for which the "homogenization at $-1$" of $p_G({\bf n})$ is real-stable (equivalently, Lorentzian, or strongly/completely log-concave), if and only if the normalization of $p_G(-{\bf n})$ is strongly Rayleigh.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript defines the blowup-polynomial p_X({n_x}) for any finite metric space X as the determinant of the distance matrix of the blowup X[n] after dividing out an explicit exponential factor. It proves that p_X is always a multi-affine real-stable polynomial in the variables n_x and associates to it a delta-matroid. Specializing to connected graphs G, the paper shows that p_G (together with its symmetries) recovers G up to isometry, that the univariate specialization u_G(x) is a transform of the characteristic polynomial of the distance matrix D_G, and that complete multipartite graphs are precisely those for which the homogenization of p_G at -1 is real-stable (equivalently Lorentzian) if and only if the normalization of p_G(-n) is strongly Rayleigh.

Significance. If the stated theorems hold, the construction supplies a new polynomial invariant of metric spaces that is always real-stable, links distance spectra of graphs to stable polynomials, and yields a combinatorial characterization of complete multipartite graphs. The explicit recovery of G from p_G and the delta-matroid association are concrete contributions that could be of interest to researchers working at the interface of metric geometry, algebraic combinatorics, and stability theory.

minor comments (2)
  1. The abstract states that p_X is obtained 'by computing the determinant of the distance matrix of X[n] and removing an exponential factor,' but the precise form of the exponential factor (and the normalization that makes the result a polynomial) is not restated in the abstract; a one-sentence clarification would help readers.
  2. The claim that the delta-matroid associated to a tree does not generalize to all graphs is stated without an explicit counter-example graph in the abstract; adding a brief parenthetical example would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending minor revision. No major comments appear in the provided report, so there are no specific points requiring point-by-point response or rebuttal.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The blowup-polynomial is defined directly as det(D_{X[n]}) divided by an explicit exponential factor in the sizes n_x. The paper then proves (as theorems) that this expression is in fact a multi-affine polynomial, that it is real-stable for arbitrary finite metrics, and that the graph specializations recover G up to isometry and relate to the distance spectrum. These are independent derivations from the concrete matrix definition rather than tautological reductions, self-citations, or fitted inputs renamed as predictions. No load-bearing step collapses to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The central claims rest on standard facts about determinants and real polynomials together with the new definition of the blowup construction; no free parameters or invented physical entities appear.

axioms (2)
  • standard math Determinant of a matrix whose entries are linear in the n_x variables yields a polynomial after division by the exponential prefactor.
    Invoked when defining p_X from det(D_{X[n]}).
  • domain assumption Real-stability is preserved under the operations used to obtain p_X from the distance matrix.
    Required for the main theorem on real-stability of p_X.
invented entities (2)
  • blowup-polynomial p_X no independent evidence
    purpose: New invariant extracted from blowup distance matrices
    Introduced as the central object of study; no independent evidence outside the paper.
  • delta-matroid associated to X no independent evidence
    purpose: Combinatorial structure extracted from the blowup-polynomial
    Newly associated to each metric space; no external verification supplied.

pith-pipeline@v0.9.0 · 5910 in / 1390 out tokens · 21076 ms · 2026-05-24T13:28:56.202607+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    Anari, S

    N. Anari, S. Oveis Gharan, and C. Vinzant. Log-concave po lynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. FOCS 2018 Proc. (59th Annual IEEE Symposium), pp. 35–46, 2018

    work page 2018

  2. [2]

    Aouchiche and P

    M. Aouchiche and P. Hansen. Distance spectra of graphs: a survey. Linear Algebra Appl. , 458:301–386, 2014

    work page 2014

  3. [3]

    Bochnak, M

    J. Bochnak, M. Coste, and M.-F. Roy. G´ eom´ etrie alg´ ebrique r´ eelle. In: Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 12, x+376 pp., Springer–Verlag, Berlin, Heidelberg, 1987

    work page 1987

  4. [4]

    Borcea and P

    J. Borcea and P. Br¨ and´ en. Applications of stable polyn omials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products. Duke Math. J. , 143(2):205–223, 2008

    work page 2008

  5. [5]

    Borcea and P

    J. Borcea and P. Br¨ and´ en. P´ olya–Schur master theorems for circular domains and their boundaries. Ann. of Math. (2) , 170(1):465–492, 2009

    work page 2009

  6. [6]

    Borcea and P

    J. Borcea and P. Br¨ and´ en. The Lee–Yang and P´ olya–Schur programs. I. Linear operators preserving stability. Invent. Math. , 177(3):541–569, 2009

    work page 2009

  7. [7]

    Borcea, P

    J. Borcea, P. Br¨ and´ en, and T.M. Liggett. Negative dependence and the geometry of polynomials. J. Amer. Math. Soc., 22(2):521–567, 2009

    work page 2009

  8. [8]

    A. Bouchet. Greedy algorithms and symmetric matroids. Math Progr., 38:147–159, 1987

    work page 1987

  9. [9]

    A. Bouchet. Representability of ∆-matroids. In: Proc. 6th Hungarian Coll. Combin. 1987 , Colloq. Math. Soc. J´ anos Bolyai, 52:167–182, 1988

    work page 1987

  10. [10]

    Br¨ and´ en

    P. Br¨ and´ en. Polynomials with the half-plane property and matroid theory. Adv. in Math. , 216(1):302–320, 2007

    work page 2007

  11. [11]

    Br¨ and´ en and J

    P. Br¨ and´ en and J. Huh. Lorentzian polynomials.Ann. of Math. (2) , 192(3):821–891, 2020

    work page 2020

  12. [12]

    A. Cayley. On a theorem in the geometry of position. Cambridge Math. J. , II:267–271, 1841

    work page

  13. [13]

    Cheeger, B

    J. Cheeger, B. Kleiner, and A. Schioppa. Infinitesimal s tructure of differentiability spaces, and metric differen- tiation. Anal. Geom. Metric Spaces , 4(1):104–159, 2016. BLOWUP-POLYNOMIAL OF A METRIC SPACE: CONNECTIONS TO STABLE POLYNOMIALS AND GRAPHS 33

    work page 2016

  14. [14]

    Choe, J.G

    Y.-B. Choe, J.G. Oxley, A.D. Sokal, and D.G. Wagner. Hom ogeneous multivariate polynomials with the half- plane property. Adv. in Appl. Math. , 32(1–2):88–187, 2004

    work page 2004

  15. [15]

    Choudhury and A

    P.N. Choudhury and A. Khare. Distance matrices of a tree : two more invariants, and in a unified framework. Preprint, arXiv:1903.11566, 2019

    work page arXiv 1903

  16. [16]

    Descartes

    R. Descartes. Le G´ eom´ etrie. Appendix toDiscours de la m´ ethode, 1637

    work page

  17. [17]

    Drury and H

    S. Drury and H. Lin. Some graphs determined by their dist ance spectrum. Electr. J. Linear Alg. , 34:320–330, 2018

    work page 2018

  18. [18]

    Fr´ echet

    M.R. Fr´ echet. Les dimensions d’un ensemble abstrait. Math. Ann. , 68:145–168, 1910

    work page 1910

  19. [19]

    Graham and L

    R.L. Graham and L. Lov´ asz. Distance matrix polynomial s of trees. Adv. in Math. , 29(1):60–88, 1978

    work page 1978

  20. [20]

    Graham and H.O

    R.L. Graham and H.O. Pollak. On the addressing problem f or loop switching. Bell System Tech. J. , 50:2495–2519, 1971

    work page 1971

  21. [21]

    Guillot, A

    D. Guillot, A. Khare, and B. Rajaratnam. Critical expon ents of graphs. J. Combin. Th. Ser. A , 139:30–58, 2016

    work page 2016

  22. [22]

    L. Gurvits. On multivariate Newton-like inequalities . Adv. in Combin. Math. , Springer, Berlin, pp. 61–78, 2009

    work page 2009

  23. [23]

    Hatami, J

    H. Hatami, J. Hirst, and S. Norine. The inducibility of b low-up graphs. J. Combin. Th. Ser. B , 109:196–212, 2014

    work page 2014

  24. [24]

    J. Kim, D. K¨ uhn, D. Osthus, and M. Tyomkyn. A blow-up lem ma for approximate decompositions. Trans. Amer. Math. Soc. , 371(7):4655–4742, 2019

    work page 2019

  25. [25]

    Koml´ os, G.N

    J. Koml´ os, G.N. S´ ark¨ ozy, and E. Szemer´ edi. Blow-uplemma. Combinatorica, 17:109–123, 1997

    work page 1997

  26. [26]

    Laguerre

    E. Laguerre. Sur les fonctions du genre z´ ero et du genre un. C. R. Acad. Sci. Paris , 95:828–831, 1882

    work page

  27. [27]

    H. Lin, Y. Hong, J. Wang, and J. Shu. On the distance spect rum of graphs. Linear Algebra Appl. , 439(6):1662– 1669, 2013

    work page 2013

  28. [28]

    H. Liu. Extremal graphs for blow-ups of cycles and trees . Electr. J. Combin. , 20(1): art. # P65, 16 pp., 2013

    work page 2013

  29. [29]

    Marcus, D.A

    A.W. Marcus, D.A. Spielman, and N. Srivastava. Interla cing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2) , 182(1):307–325, 2015

    work page 2015

  30. [30]

    Marcus, D.A

    A.W. Marcus, D.A. Spielman, and N. Srivastava. Interla cing families II. Mixed characteristic polynomials and the Kadison-Singer problem. Ann. of Math. (2) , 182(1):327–350, 2015

    work page 2015

  31. [31]

    K. Menger. Untersuchungen ¨ uber allgemeine Metrik. Math. Ann. : Part I : Vol. 100:75–163, 1928; Part II : Vol. 103:466–501, 1930

    work page 1928

  32. [32]

    K. Menger. New foundation of Euclidean geometry. Amer. J. Math. , 53(4):721–745, 1931

    work page 1931

  33. [33]

    G. P´ olya. ¨Uber Ann¨ aherung durch Polynome mit lauter reellen Wurzeln. Rend. Circ. Mat. Palermo , 36:279–295, 1913

    work page 1913

  34. [34]

    P´ olya and I

    G. P´ olya and I. Schur. ¨Uber zwei Arten von Faktorenfolgen in der Theorie der algebr aischen Gleichungen. J. reine angew. Math. , 144:89–113, 1914

    work page 1914

  35. [35]

    Royle and A.D

    G. Royle and A.D. Sokal. The Brown–Colbourn conjecture on zeros of reliability polynomials is false. J. Combin. Th. Ser. B , 91(2):345–360, 2004

    work page 2004

  36. [36]

    A.D. Sokal. Bounds on the complex zeros of (di)chromati c polynomials and Potts-model partition functions. Combin. Probab. Comput. , 10(1):41–77, 2001

    work page 2001

  37. [37]

    A.D. Sokal. The multivariate Tutte polynomial (alias P otts model) for graphs and matroids. In: Surveys in Combinatorics 2005 , London Math. Soc. Lect. Notes, 327:173–226 (chap. 8), 2005

    work page 2005

  38. [38]

    Sur la d´ efinition axiomatique d’une classe d’espace dis- tanci´ es vectoriellement applicable sur l’espace de Hilbe rt

    I.J. Schoenberg. Remarks to Maurice Fr´ echet’s articl e “Sur la d´ efinition axiomatique d’une classe d’espace dis- tanci´ es vectoriellement applicable sur l’espace de Hilbe rt”. Ann. of Math. (2) , 36(3):724–732, 1935

    work page 1935

  39. [39]

    Schoenberg

    I.J. Schoenberg. Metric spaces and positive definite fu nctions. Trans. Amer. Math. Soc. , 44(3):522–536, 1938

    work page 1938

  40. [40]

    D.E. Speyer. Horn’s problem, Vinnikov curves, and the h ive cone. Duke Math. J. , 127(3):395–427, 2005

    work page 2005

  41. [41]

    D.G. Wagner. Zeros of reliability polynomials and f -vectors of matroids. Combin. Probab. Comput., 9(2):167–190, 2000

    work page 2000

  42. [42]

    Wagner and Y

    D.G. Wagner and Y. Wei. A criterion for the half-plane pr operty. Discrete Math. , 309(6):1385–1390, 2009. (P.N. Choudhury) Indian Institute of Science, Bangalore 560012, India Email address : projeshc@iisc.ac.in (A. Khare) Indian Institute of Science; Analysis and Probability Rese arch Group; Bangalore 560012, India Email address : khare@iisc.ac.in

    work page 2009