Maximum Generalised Roundness of Graph Metric Spaces

dc.contributor.advisor Doust, Ian en_US
dc.contributor.advisor Grossman, Pinhas en_US De Silva, Raveen en_US 2022-03-23T14:21:26Z 2022-03-23T14:21:26Z 2020 en_US
dc.description.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. en_US
dc.language English
dc.language.iso EN en_US
dc.publisher UNSW, Sydney en_US
dc.rights CC BY-NC-ND 3.0 en_US
dc.rights.uri en_US
dc.subject.other Maximum Generalised Roundness en_US
dc.subject.other Graph Metric Spaces en_US
dc.title Maximum Generalised Roundness of Graph Metric Spaces en_US
dc.type Thesis en_US
dcterms.accessRights open access
dcterms.rightsHolder De Silva, Raveen
dspace.entity.type Publication en_US
unsw.relation.faculty Science
unsw.relation.originalPublicationAffiliation De Silva, Raveen, Mathematics & Statistics, Faculty of Science, UNSW en_US
unsw.relation.originalPublicationAffiliation Doust, Ian, Mathematics & Statistics, Faculty of Science, UNSW en_US
unsw.relation.originalPublicationAffiliation Grossman, Pinhas, Mathematics & Statistics, Faculty of Science, UNSW en_US School of Mathematics & Statistics *
unsw.thesis.degreetype PhD Doctorate en_US
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
public version.pdf
2.31 MB
Resource type