Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2025-01-02T19:39:13.033Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Analysis on metric spaces Graph theory Basic linear algebra Polynomials, rational functions

Published online by Cambridge University Press:  09 November 2023

Projesh Nath Choudhury  and
Apoorva Khare Open the ORCID record for Apoorva Khare [Opens in a new window]
Projesh Nath Choudhury*
Affiliation:
Department of Mathematics, Indian Institute of Technology Gandhinagar, Palaj, Gandhinagar 382055, India
Apoorva Khare
Affiliation:
Department of Mathematics, Indian Institute of Science, Bengaluru 560012, India and Analysis and Probability Research Group, Bangalore 560012, India e-mail: [email protected]
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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[\mathbf {n}]$ – which contains $n_x$ copies of each point x – by computing the determinant of the distance matrix of $X[\mathbf {n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X(\mathbf {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(\mathbf { n})$ is real-stable (equivalently, Lorentzian, or strongly/completely log-concave), if and only if the normalization of $p_G(-\mathbf { n})$ is strongly Rayleigh.

Keywords

blowup-polynomialreal-stable polynomialdelta-matroiddistance spectrum of a graphZariski density

MSC classification

Primary: 26C10: Polynomials 05C31: Graph polynomials
Secondary: 30L05: Geometric embeddings of metric spaces 15A15: Determinants, permanents, other special matrix functions 05C12: Distance in graphs 05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Type
Article
Information
Canadian Journal of Mathematics , Volume 76 , Issue 6 , December 2024 , pp. 2073 - 2114
Check for updates
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of The Canadian Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

P. N. Choudhury was partially supported by INSPIRE Faculty Fellowship research grant DST/INSPIRE/04/2021/002620 (DST, Govt. of India), IIT Gandhinagar Internal Project grant IP/IITGN/MATH/PNC/2223/25, C.V. Raman Postdoctoral Fellowship 80008664 (IISc), and National Post-Doctoral Fellowship (NPDF) PDF/2019/000275 from SERB (Govt. of India). A. Khare was partially supported by Ramanujan Fellowship grant SB/S2/RJN-121/2017, MATRICS grant MTR/2017/000295, and SwarnaJayanti Fellowship grants SB/SJF/2019-20/14 and DST/SJF/MS/2019/3 from SERB and DST (Govt. of India), by a Shanti Swarup Bhatnagar Award from CSIR (Govt. of India), by grant F.510/25/CAS-II/2018(SAP-I) from UGC (Govt. of India), and by the DST FIST program 2021 (TPN–700661).

References

Anari, N., Oveis Gharan, S., and Vinzant, C., Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids . In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science, IEEE, New York, 2018, pp. 35–46.CrossRefGoogle Scholar
Anari, N., Oveis Gharan, S., and Vinzant, C., Log-concave polynomials, I: Entropy and a deterministic approximation algorithm for counting bases of matroids . Duke Math. J. 170(2021), 3459–3504.CrossRefGoogle Scholar
Aouchiche, M. and Hansen, P., Distance spectra of graphs: A survey . Linear Algebra Appl. 458(2014), 301–386.CrossRefGoogle Scholar
Bochnak, J., Coste, M., and Roy, M.-F., Géométrie algébrique réelle . In: Ergebnisse der Mathematik und ihrer Grenzgebiete. Vol. 12, Springer, Berlin, 1987.Google Scholar
Borcea, J. and Brändén, P., Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products . Duke Math. J. 143(2008), 205–223.CrossRefGoogle Scholar
Borcea, J. and Brändén, P., Pólya–Schur master theorems for circular domains and their boundaries . Ann. of Math. (2) 170(2009), 465–492.CrossRefGoogle Scholar
Borcea, J. and Brändén, P., The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability . Invent. Math. 177(2009), 541–569.CrossRefGoogle Scholar
Borcea, J., Brändén, P., and Liggett, T. M., Negative dependence and the geometry of polynomials . J. Amer. Math. Soc. 22(2009), 521–567.CrossRefGoogle Scholar
Bouchet, A., Greedy algorithms and symmetric matroids . Math Progr. 38(1987), 147–159.CrossRefGoogle Scholar
Bouchet, A., Representability of $\varDelta$ -matroids. In: Proceedings of the 6th Hungarian Colloquium of Combinatorics, Colloquia Mathematica Societatis János Bolyai, North-Holland, Amsterdam, 52, 1988, pp. 167–182.Google Scholar
Brändén, P., Polynomials with the half-plane property and matroid theory . Adv. in Math. 216(2007), 302–320.CrossRefGoogle Scholar
Brändén, P. and Huh, J., Lorentzian polynomials . Ann. of Math. (2) 192(2020), 821–891.CrossRefGoogle Scholar
Cayley, A., On a theorem in the geometry of position . Cambridge Math. J., II(1841), 267–271.Google Scholar
Cheeger, J., Kleiner, B., and Schioppa, A., Infinitesimal structure of differentiability spaces, and metric differentiation . Anal. Geom. Metric Spaces 4(2016), 104–159.Google Scholar
Choe, Y.-B., Oxley, J. G., Sokal, A. D., and Wagner, D. G., Homogeneous multivariate polynomials with the half-plane property . Adv. in Appl. Math. 32(2004), 88–187.CrossRefGoogle Scholar
Choudhury, P. N. and Khare, A., Distance matrices of a tree: two more invariants, and in a unified framework . Eur. J. Combin. 115(2024), 103787.CrossRefGoogle Scholar
Descartes, R., Le Géométrie. Appendix to Discours de la méthode, 1637.Google Scholar
Drury, S. and Lin, H., Some graphs determined by their distance spectrum . Electr. J. Linear Alg. 34(2018), 320–330.CrossRefGoogle Scholar
Fréchet, M. R., Les dimensions d’un ensemble abstrait . Math. Ann. 68(1910), 145–168.CrossRefGoogle Scholar
Graham, R. L. and Lovász, L., Distance matrix polynomials of trees . Adv. in Math. 29(1978), 60–88.CrossRefGoogle Scholar
Graham, R. L. and Pollak, H. O., On the addressing problem for loop switching . Bell System Tech. J. 50(1971), 2495–2519.CrossRefGoogle Scholar
Guillot, D., Khare, A., and Rajaratnam, B., Critical exponents of graphs . J. Combin. Th. Ser. A 139(2016), 30–58.CrossRefGoogle Scholar
Gurvits, L., On multivariate Newton-like inequalities . In: Kotsireas, I. and Zima, E. (eds.), Advances in combinatorial mathematics, Springer, Berlin, 2009, pp. 61–78.CrossRefGoogle Scholar
Hatami, H., Hirst, J., and Norine, S., The inducibility of blow-up graphs . J. Combin. Th. Ser. B 109(2014), 196–212.CrossRefGoogle Scholar
Kim, J., Kühn, D., Osthus, D., and Tyomkyn, M., A blow-up lemma for approximate decompositions . Trans. Amer. Math. Soc. 371(2019), 4655–4742.CrossRefGoogle Scholar
Komlós, J., Sárközy, G. N., and Szemerédi, E., Blow-up lemma . Combinatorica 17(1997), 109–123.CrossRefGoogle Scholar
Laguerre, E., Sur les fonctions du genre zéro et du genre un . C. R. Acad. Sci. Paris 95(1882), 828–831.Google Scholar
Lin, H., Hong, Y., Wang, J., and Shu, J., On the distance spectrum of graphs . Linear Algebra Appl. 439(2013), 1662–1669.CrossRefGoogle Scholar
Liu, H., Extremal graphs for blow-ups of cycles and trees . Electr. J. Combin. 20(2013), P65.CrossRefGoogle Scholar
Marcus, A. W., Spielman, D. A., and Srivastava, N., Interlacing families I: Bipartite Ramanujan graphs of all degrees . Ann. of Math. (2) 182(2015), 307–325.CrossRefGoogle Scholar
Marcus, A. W., Spielman, D. A., and Srivastava, N., Interlacing families II. Mixed characteristic polynomials and the Kadison–Singer problem . Ann. of Math. (2) 182(2015), 327–350.CrossRefGoogle Scholar
Menger, K., Untersuchungen über allgemeine Metrik . Math. Ann. Part I: 100(1928), 75–163; Part II: 103(1930), 466–501.CrossRefGoogle Scholar
Menger, K., New foundation of Euclidean geometry . Amer. J. Math. 53(1931), 721–745.CrossRefGoogle Scholar
Pólya, G., Über Annäherung durch Polynome mit lauter reellen Wurzeln . Rend. Circ. Mat. Palermo 36(1913), 279–295.CrossRefGoogle Scholar
Pólya, G. and Schur, I., Über zwei Arten von Faktorenfolgen in der Theorie der algebraischen Gleichungen . J. Reine Angew. Math. 144(1914), 89–113.Google Scholar
Royle, G. and Sokal, A. D., The Brown–Colbourn conjecture on zeros of reliability polynomials is false . J. Combin. Th. Ser. B 91(2004), 345–360.CrossRefGoogle Scholar
Schoenberg, I. J., Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espace distanciés vectoriellement applicable sur l’espace de Hilbert ”. Ann. of Math. (2) 36(1935), 724–732.CrossRefGoogle Scholar
Schoenberg, I. J., Metric spaces and positive definite functions . Trans. Amer. Math. Soc. 44(1938), 522–536.CrossRefGoogle Scholar
Sokal, A. D., Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions . Combin. Probab. Comput. 10(2001), 41–77.CrossRefGoogle Scholar
Sokal, A. D., The multivariate Tutte polynomial (alias Potts model) for graphs and matroids . In: Webb, B. (ed.), Surveys in combinatorics 2005, London Mathematical Society Lecture Note Series, 327, Cambridge University Press, Cambridge, 2005, pp. 173–226.CrossRefGoogle Scholar
Speyer, D. E., Horn’s problem, Vinnikov curves, and the hive cone . Duke Math. J. 127(2005), 395–427.CrossRefGoogle Scholar
Wagner, D. G., Zeros of reliability polynomials and $f$ -vectors of matroids . Combin. Probab. Comput. 9(2000), 167–190.CrossRefGoogle Scholar
Wagner, D. G. and Wei, Y., A criterion for the half-plane property . Discrete Math. 309(2009), 1385–1390.CrossRefGoogle Scholar