A problem on distance matrices of subsets of the Hamming cube

Doust, Ian; Wolf, Reinhard

doi:10.1090/bproc/122

A problem on distance matrices of subsets of the Hamming cube
HTML articles powered by AMS MathViewer

by Ian Doust and Reinhard Wolf HTML | PDF

Proc. Amer. Math. Soc. Ser. B 9 (2022), 125-134

Abstract:

Let $D$ denote the distance matrix for an $n+1$ point metric space $(X,d)$. In the case that $X$ is an unweighted metric tree, the sum of the entries in $D^{-1}$ is always equal to $2/n$. Such trees can be considered as affinely independent subsets of the Hamming cube $H_n$, and it was conjectured that the value $2/n$ was minimal among all such subsets. In this paper we confirm this conjecture and give a geometric interpretation of our result which applies to any subset of $H_n$.

References

Ralph Alexander and Kenneth B. Stolarsky, Extremal problems of distance geometry related to energy integrals, Trans. Amer. Math. Soc. 193 (1974), 1–31. MR 350629, DOI 10.1090/S0002-9947-1974-0350629-3
Ian Doust, Gavin Robertson, Alan Stoneham, and Anthony Weston, Distance matrices of subsets of the Hamming cube, Indag. Math. (N.S.) 32 (2021), no. 3, 646–657. MR 4246131, DOI 10.1016/j.indag.2021.01.004
R. L. Graham and L. Lovász, Distance matrix polynomials of trees, Adv. in Math. 29 (1978), no. 1, 60–88. MR 480119, DOI 10.1016/0001-8708(78)90005-1
R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J. 50 (1971), 2495–2519. MR 289210, DOI 10.1002/j.1538-7305.1971.tb02618.x
R. L. Graham and P. M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985), no. 2, 527–536. MR 776391, DOI 10.1090/S0002-9947-1985-0776391-5
R. L. Graham and P. M. Winkler, Corrigendum to: “On isometric embeddings of graphs” [Trans. Amer. Math. Soc. 288 (1985), no. 2, 527–536; MR0776391 (86f:05055b)], Trans. Amer. Math. Soc. 294 (1986), no. 1, 379. MR 819955, DOI 10.1090/S0002-9947-1986-0819955-3
C. J. Lennard, A. M. Tonge, and A. Weston, Generalized roundness and negative type, Michigan Math. J. 44 (1997), no. 1, 37–45. MR 1439667, DOI 10.1307/mmj/1029005619
Mathav Kishore Murugan, Supremal $p$-negative type of vertex transitive graphs, J. Math. Anal. Appl. 391 (2012), no. 2, 376–381. MR 2903138, DOI 10.1016/j.jmaa.2012.02.042
Peter Nickolas and Reinhard Wolf, Distance geometry in quasihypermetric spaces. I, Bull. Aust. Math. Soc. 80 (2009), no. 1, 1–25. MR 2520521, DOI 10.1017/S0004972708000932
Peter Nickolas and Reinhard Wolf, Distance geometry in quasihypermetric spaces. II, Math. Nachr. 284 (2011), no. 2-3, 332–341. MR 2790892, DOI 10.1002/mana.200710206
Peter Nickolas and Reinhard Wolf, Distance geometry in quasihypermetric spaces. III, Math. Nachr. 284 (2011), no. 5-6, 747–760. MR 2663766, DOI 10.1002/mana.200810216
P. Nickolas and R. Wolf, Finite quasihypermetric spaces, Acta Math. Hungar. 124 (2009), no. 3, 243–262. MR 2525563, DOI 10.1007/s10474-009-8182-2
Stephen Sánchez, On the supremal $p$-negative type of finite metric spaces, J. Math. Anal. Appl. 389 (2012), no. 1, 98–107. MR 2876484, DOI 10.1016/j.jmaa.2011.11.043
I. J. Schoenberg, Metric spaces and positive definite functions, Trans. Amer. Math. Soc. 44 (1938), no. 3, 522–536. MR 1501980, DOI 10.1090/S0002-9947-1938-1501980-0
J. H. Wells and L. R. Williams, Embeddings and extensions in analysis, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84, Springer-Verlag, New York-Heidelberg, 1975. MR 0461107, DOI 10.1007/978-3-642-66037-5
Reinhard Wolf, On the gap of finite metric spaces of $p$-negative type, Linear Algebra Appl. 436 (2012), no. 5, 1246–1257. MR 2890917, DOI 10.1016/j.laa.2011.08.031
Reinhard Wolf, Estimating the gap of finite metric spaces of strict $p$-negative type, Linear Algebra Appl. 556 (2018), 171–199. MR 3842579, DOI 10.1016/j.laa.2018.07.005