Generalized roundness of vertex transitive graphs

Abstract

We study the generalized roundness of finite metric spaces whose distance matrix $D$ has the property that every row of $D$ is a permutation of the first row. The analysis provides a way to characterize subsets of the Hamming cube $\{0,1{\}}^n\subset {\ell }_1^{(n)}$ ($n\ge 1$) that have strict $1$-negative type. The result can be stated in two ways: a subset $S = \{ \vc{x}_0,\vc{x}_1,\ldots,\vc{x}_k \}$ of the Hamming cube $\{0,1{\}}^n\subset {\ell }_1^{(n)}$ has generalized roundness one if and only if the vectors $\{ \vc{x}_1 - \vc{x}_0,\vc{x}_2 - \vc{x}_0,\ldots,\vc{x}_k - \vc{x}_0 \}$ are linearly dependent in ${\mathbb{R}}^n$. Equivalently, $S$ has strict $1$-negative type if and only if the vectors $\{ \vc{x}_1 - \vc{x}_0,\vc{x}_2 - \vc{x}_0,\ldots,\vc{x}_k - \vc{x}_0 \}$ are linearly independent in ${\mathbb{R}}^n$.