Maximum Generalised Roundness of Graph Metric Spaces

Abstract

This thesis examines the maximum generalised roundness properties of metric spaces arising from graphs. The equivalent concepts of $p$-negative type and generalised roundness $p$, introduced by Schoenberg and Enflo respectively, have been used for several decades in the field of distance geometry, primarily to obstruct embeddings of metric spaces isometrically (or with some distortion) into Euclidean space. Given a metric space $(X,d)$, we are particularly interested in the calculation of its maximum generalised roundness $\wp(X,d)$, and many existing results from various authors are expounded in this thesis. A relatively recent formula of S\'{a}nchez provides a method to numerically calculate the quantity of interest, but implementing this in practice involves a number of previously unforeseen difficulties. In this thesis we develop a robust algorithm which enables the efficient numerical calculation of $\wp(X,d)$ for large sets of finite metric spaces.

We focus in particular on metric spaces constructed from graphs, usually with the path metric, in order to relate the maximum generalised roundness value to properties of the underlying graph. Many existing results describe the extremal values of the maximum generalised roundness of trees or connected graphs, but little is known about the values for `typical' members of these classes. Equipped with the earlier algorithm, we are able to quickly and reliably calculate the maximum generalised roundness of graphs sampled at random from these families, and form hypotheses from the resulting data. We are able to prove that large random trees have maximum generalised roundness arbitrarily close to $1$ almost surely, and provide more specific probabilistic results with explicit bounds. We also prove that for large random graphs, the maximum generalised roundness is arbitrarily close to $0$ almost surely. In each case, we additionally state stronger heuristic conclusions which are supported by the empirical evidence, but for which we do not yet have rigorous proofs. We also present several partial results, conjectures and unexplained phenomena from our earlier investigations as well as peripheral work on infinite trees and planar graphs.