Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistance matrices of subsets of the Hamming cube
161
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Graham and Winkler derived a formula for the determinant of the distance matrix of a full-dimensional set of $n + 1$ points ${ x_{0}, x_{1}, ldots , x_{n} }$ in the Hamming cube $H_{n} = ( { 0,1 }^{n}, ell_{1} )$. In this article we derive a formula for the determinant of the distance matrix $D$ of an arbitrary set of $m + 1$ points ${ x_{0}, x_{1}, ldots , x_{m} }$ in $H_{n}$. It follows from this more general formula that $det (D) ot= 0$ if and only if the vectors $x_{0}, x_{1}, ldots , x_{m}$ are affinely independent. Specializing to the case $m = n$ provides new insights into the original formula of Graham and Winkler. A significant difference that arises between the cases $m < n$ and $m = n$ is noted. We also show that if $D$ is the distance matrix of an unweighted tree on $n + 1$ vertices, then $langle D^{-1} mathbf{1}, mathbf{1} rangle = 2/n$ where $mathbf{1}$ is the column vector all of whose coordinates are $1$. Finally, we derive a new proof of Murugans classification of the subsets of $H_{n}$ that have strict $1$-negative type.
rate research
Read More
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$.
The Lipschitz geometry of segments of the infinite Hamming cube is studied. Tight estimates on the distortion necessary to embed the segments into spaces of continuous functions on countable compact metric spaces are given. As an application, the first nontrivial lower bounds on the $C(K)$-distortion of important classes of separable Banach spaces, where $K$ is a countable compact space in the family $ { [0,omega],[0,omegacdot 2],dots, [0,omega^2], dots, [0,omega^kcdot n],dots,[0,omega^omega]} ,$ are obtained.
Let $mathcal{M}(Omega, mu)$ denote the algebra of all scalar-valued measurable functions on a measure space $(Omega, mu)$. Let $B subset mathcal{M}(Omega, mu)$ be a set of finitely supported measurable functions such that the essential range of each $f in B$ is a subset of ${ 0,1 }$. The main result of this paper shows that for any $p in (0, infty)$, $B$ has strict $p$-negative type when viewed as a metric subspace of $L_{p}(Omega, mu)$ if and only if $B$ is an affinely independent subset of $mathcal{M}(Omega, mu)$ (when $mathcal{M}(Omega, mu)$ is considered as a real vector space). It follows that every two-valued (Schauder) basis of $L_{p}(Omega, mu)$ has strict $p$-negative type. For instance, for each $p in (0, infty)$, the system of Walsh functions in $L_{p}[0,1]$ is seen to have strict $p$-negative type. The techniques developed in this paper also provide a systematic way to construct, for any $p in (2, infty)$, subsets of $L_{p}(Omega, mu)$ that have $p$-negative type but not $q$-negative type for any $q > p$. Such sets preclude the existence of certain types of isometry into $L_{p}$-spaces.
$H_q(n,d)$ is defined as the graph with vertex set ${mathbb Z}_q^n$ and where two vertices are adjacent if their Hamming distance is at least $d$. The chromatic number of these graphs is presented for various sets of parameters $(q,n,d)$. For the $4$-colorings of the graphs $H_2(n,n-1)$ a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust $4$-colorings of $H_2(n,n-1)$ is presented.
Within the class of reflexive Banach spaces, we prove a metric characterization of the class of asymptotic-$c_0$ spaces in terms of a bi-Lipschitz invariant which involves metrics that generalize the Hamming metric on $k$-subsets of $mathbb{N}$. We apply this characterization to show that the class of separable, reflexive, and asymptotic-$c_0$ Banach spaces is non-Borel co-analytic. Finally, we introduce a relaxation of the asymptotic-$c_0$ property, called the asymptotic-subsequential-$c_0$ property, which is a partial obstruction to the equi-coarse embeddability of the sequence of Hamming graphs. We present examples of spaces that are asymptotic-subsequential-$c_0$. In particular $T^*(T^*)$ is asymptotic-subsequential-$c_0$ where $T^*$ is Tsirelsons original space.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
