Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA problem on distance matrices of subsets of the Hamming cube
131
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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$.
rate research
Read More
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.
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.
$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.
For $ninmathbb N$ let $Theta^{(n)}$ be a random vector uniformly distributed on the unit sphere $mathbb S^{n-1}$, and consider the associated random probability measure $mu_{Theta^{(n)}}$ given by setting [ mu_{Theta^{(n)}}(A) := mathbb{P} left[ langle U, Theta^{(n)} rangle in A right],qquad U sim text{Unif}([-1,1]^n) ] for Borel subets $A$ of $mathbb{R}$. It is known that the sequence of random probability measures $mu_{Theta^{(n)}}$ converges weakly to the centered Gaussian distribution with variance $1/3$. We prove a large deviation principle for the sequence $mu_{Theta^{(n)}}$ with speed $n$ and explicit good rate rate function given by $I( u(alpha)) := - frac{1}{2} log ( 1 - ||alpha||_2^2)$ whenever $ u(alpha)$ is the law of a random variable of the form begin{align*} sqrt{1 - ||alpha||_2^2 } frac{Z}{sqrt 3} + sum_{ k = 1}^infty alpha_k U_k, end{align*} where $Z$ is standard Gaussian independent of $U_1,U_2,ldots$ which are i.i.d. $text{Unif}[-1,1]$, and $alpha_1 geq alpha_2 geq ldots $ is a non-increasing sequence of non-negative reals with $||alpha||_2<1$. We obtain a similar result for projections of the uniform distribution on the discrete cube ${-1,+1}^n$.
Our starting point is an improved version of a result of D. Hajela related to a question of Koml{o}s: we show that if $f(n)$ is a function such that $limlimits_{ntoinfty }f(n)=infty $ and $f(n)=o(n)$, there exists $n_0=n_0(f)$ such that for every $ngeqslant n_0$ and any $Ssubseteq {-1,1}^n$ with cardinality $|S|leqslant 2^{n/f(n)}$ one can find orthonormal vectors $x_1,ldots ,x_nin {mathbb R}^n$ that satisfy $$|epsilon_1x_1+cdots +epsilon_nx_n|_{infty }geqslant csqrt{log f(n)}$$ for all $(epsilon_1,ldots ,epsilon_n)in S$. We obtain analogous results in the case where $x_1,ldots ,x_n$ are independent random points uniformly distributed in the Euclidean unit ball $B_2^n$ or any symmetric convex body, and the $ell_{infty }^n$-norm is replaced by an arbitrary norm on ${mathbb R}^n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
