%\documentclass[10pt,oneside]{article} %\documentclass[10pt]{report} \documentclass[10pt]{amsart} \usepackage{amscd} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} %\usepackage{verbatim} %\usepackage[all]{xy} \title{Universality and Randomness for the Graphs and Metric Spaces} \author{A.\;M.~Vershik} \address{St.Petersburg Mathematical Institute of Russian Academy of Science\\ Fontanka 27\\ St.Petersburg, 191011\\ Russia} \email{vershik@pdmi.ras.ru} \thanks{Supported by the RF President's Grant ``Podderzhka Veduschikh Nauchnykh Shkol RF'' No. 2251.2003.1} % MISCANELLOUS ----------------------------------------------------------- \vfuzz2pt % Don't report over-full v-boxes if over-edge is small \sloppy % THEOREM Environments --------------------------------------------------- \newtheorem{thm}{Theorem}[section] %\newtheorem{thm}{Theorem}[subsection] \newtheorem{cor}[thm]{Corollary} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem{question}[]{Open Question} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \theoremstyle{remark} \newtheorem{rem}[thm]{Remark} %\newenvironment{com}{\begin{verbatim}}{\end{verbatim}} % \newtheorem{rem}[\]{Remark} %\numberwithin{equation}{subsection} \numberwithin{equation}{section} % MATH --------------------------------------------------- \DeclareMathOperator{\Adm}{Adm} \DeclareMathOperator{\diam}{diam} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\supp}{supp} \begin{document} \maketitle \tableofcontents \pagebreak %\input{graphs} \section{Universal and Random Graphs} \label{s:UNIVERSAL AND RANDOM GRAPHS} In this section we will show the existence of a denumerable, non-directed graph which is universal in the category of all countable, non-directed graphs and homogeneous (with respect to its finite subgraphs). Moreover, we will see that such a graph is determined unique up to isomorphism. This definition was done by R.~Rado. We will give the criteria of universality using incidence matrix. Then we consider the random graphs or probability measures on the set of graphs. We generalize the theorem by P.~Erd\"os and A.~R\'enyi that the random graph is universal graph with probability 1. We will describe a non-directed countable graph by a pair $\Gamma = (\Gamma,\Gamma^{(1)})$, where $\Gamma$ is the (countable) set of vertices, and $\Gamma^{(1)}\subseteq\Gamma\times\Gamma$ the set of edges. Any subset $S\subseteq\Gamma$ determines a subgraph $(S,\Gamma^{(1)}|_{S \times S})$ of $\Gamma$, which we will again denote by $S$. Given two graphs $\Gamma_i$, $i=1,2$. A mapping $\iota: \Gamma_1 \rightarrow \Gamma_2$ is called a mono-(iso)morphism, if it is one-to-one (bijective, resp.) and preserves the structure of the graph $\Gamma_1$: \[ (x,y)\in \Gamma_1^{(1)} \text{ if and only if } (\iota x, \iota y)\in \Gamma_2^{(1)}. \] In other words, $\Gamma_1$ is isomorphic to the subgraph $\iota(\Gamma_1)$ of $\Gamma_2$. Every isomorphism of $\Gamma_1$ onto itself is called automorphism. \begin{defn} A (countable, non-directed) graph $\Gamma$ is said to be \begin{itemize} \item[(1)] {\it universal}, if to any finite (non-directed) graph $F$ there exists a monomorphism $\iota: F \rightarrow \Gamma$. In other words, any finite non-directed graph is isomorphic to a subgraph of $\Gamma$. \item[(2)] {\it homogeneous}, if to any finite subgraphs $F_1$, $F_2$ of $\Gamma$, and isomorphism $\iota: F_1 \rightarrow F_2$, there exists an automorphism $\iota':\Gamma \rightarrow \Gamma$ which extends $\iota$. \end{itemize} \end{defn} \subsection{Construction of the universal graph} In the sequel, we will show that universality and homogeneity is equivalent to the following extension property: \begin{defn} A graph $\Gamma$ is said to have the \emph{extension property}, if the following holds: Given any finite graph $F$, and a one-point extension $F'$ of $F$. If there is a monomorphism $\iota: F \rightarrow \Gamma$, then $\iota$ can be extended to an monomorphism $\iota': F' \rightarrow \Gamma$, i.e. the following diagram commutes: \begin{equation*} \begin{CD} F @>{\iota \:\text{(monomorphism)}}>> \Gamma \\ @V{id}VV @V{id}VV \\ F' @>{\iota'\:\text{(monomorphism)}}>> \Gamma \end{CD}. \end{equation*} \end{defn} In other words, the graph $\Gamma$ satisfies the extension property if and only if to any finite subgraph $F$ of $\Gamma$, and any (exterior) one-point extension $F'=F \cup \{ a \}$ of $F$, there exists a point $\alpha \in \Gamma$ such that for $x\in F$ \[ (\alpha,x)\in \Gamma^{(1)} \text{ if and only if } (a,x)\in F'{^{(1)}}. \] The extension property allows us to extend locally defined isomorphisms to global isomorphisms via a so-called \emph{back and forth} argument: \begin{lem}\label{l:gr:BACK AND FORTH} Suppose $\Gamma$, $\tilde \Gamma$ are countable, non-directed graphs which have the extension property, and $F \subseteq \Gamma$ finite. Then any monomorphism $\iota: F\rightarrow \tilde{\Gamma}$ can be extended to an isomorphism $\iota': \Gamma \rightarrow \tilde{\Gamma}$. \end{lem} \begin{proof} Write $\Gamma = \{x_1, x_2, \ldots\}$ and $\tilde \Gamma =\{y_1, y_2, \ldots \}$. Denote $F_1 = F$, $G_1 = \iota (F_1)$, and $\iota_1 = \iota : F_1 \rightarrow G_1$. Define $G_2 = G_1 \cup \{ y_1 \}$. By the extension property, $\iota_1^{-1}: G_1 \rightarrow F_1$ extends to a monomorphism $\iota_2^{-1}: G_2 \rightarrow F_2$ onto a subset $F_2 \supseteq F_1$. Now define $F_3 = F_2 \cup \{ x_1 \}$. Again there is a monomorphism $\iota_3: F_3 \rightarrow G_3$ onto a subset $G_3 \supseteq G_2$. Take $G_4 = G_3 \cup \{ y_2 \}$. Continuing in the same manner as above, we can construct inductively subgraphs \[ F_1 \subseteq F_2 \subseteq \cdots \subseteq F_n \subseteq \cdots \subseteq \Gamma \] with \[ F_n \supseteq \{x_k : 1 \leq k \leq \frac{n-1}{2}\}, \] subgraphs \[ G_1 \subseteq G_2 \subseteq \cdots \subseteq G_n \subseteq \cdots \subseteq \tilde{\Gamma} \] satisfying \[ G_n \supseteq \{y_k: 1 \leq k \leq \frac{n}{2}\}, \] and isomorphisms $\iota_n: F_n\rightarrow G_n$, \[ \iota=\iota_1 \subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq \cdots \] The mapping $\iota_\infty = \bigcup_{n=1}^\infty \iota_n$ maps $\bigcup_{n=1}^\infty F_n = \Gamma$ isomorphically onto $\bigcup_{n=1}^\infty G_n = \tilde \Gamma$. \end{proof} \begin{thm}\label{t:gr:U GRAPH UNIQUE} A countable, non-directed graph is universal and homogeneous if and only if it has the extension property. Two such graphs are isomorphic. \end{thm} \begin{proof} Any universal and homogeneous graph $\Gamma$ has the extension property: By universality there is an embedding $\kappa: F_2\rightarrow M$. Define $i:\kappa(F_1)\rightarrow\iota(M_1)$, $i = \iota\circ\kappa^{-1}$. Now, choose an automorphism $J:M\rightarrow M$ which extends $i$. The mapping $J\circ\kappa: F_2\rightarrow M$ is an extension of $\iota$. Conversely, if $\Gamma$ has the extension property, then it is obviously universal. Moreover, if $\iota: F \rightarrow F'$ is an isomorphism between finite subgraphs of $\Gamma$, then Lemma \ref{l:gr:BACK AND FORTH} (setting $\Gamma=\tilde \Gamma$) shows that $\iota$ can be extended to a global automorphism $\iota': \Gamma \rightarrow \Gamma$. Hence $\Gamma$ is homogeneous. Suppose $\tilde\Gamma$ is another countable graph which satisfies the extension property. To show that $\Gamma$ and $\tilde\Gamma$ are isomorphic, choose any $a\in\Gamma$, $\tilde a\in\tilde\Gamma$, and apply Lemma \ref{l:gr:BACK AND FORTH} to the monomorphism $\iota: \{a\} \rightarrow \tilde \Gamma$, which maps $a$ to $\tilde a$. \end{proof} \begin{rem} \emph{A non-directed countable graph $\Gamma$ which has the extension property is universal in the category of all countable non-directed graphs, i.e. every countable, non-directed graph $\Gamma'$ can be embedded into $\Gamma$.} \end{rem} Consider a countable, non-directed graph $(\Gamma, \Gamma^{(1)})$, $\Gamma=\{x_1,x_2,x_2,\ldots\}$. We define its incidence matrix $m_\Gamma=(\varepsilon_{ij})_{i,j=1}^\infty\in \{0,1\}^{\mathbb N\times\mathbb N}$ by \begin{equation}\label{e:gr:INCIDENCE MATRIX} \varepsilon_{ij} = \begin{cases} 1 & \text{ if } (x_i,x_j)\in\Gamma^{(1)} \\ 0 & \text{ otherwise} \end{cases}. \end{equation} Of course the definition of $m_\Gamma$ depends on the order of the $x_i$. \begin{defn}\label{d:gr:UNIVERSAL INC MAT} An incidence matrix $(\varepsilon_{ij})_{i,j=1}^\infty$ is said to be \emph{ universal}, if for every $n\in\mathbb N$ \begin{equation}\label{e:gr:UNIV INCID MAT1} \{ (\varepsilon_{1k},\varepsilon_{2k},\ldots,\varepsilon_{nk}) : k > n \} = \{0,1\}^n. \end{equation} In other words, every finite binary word $(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)$ occurs infinitely often: \begin{equation}\label{e:gr:UNIV INCID MAT2} (\varepsilon_{1k},\varepsilon_{2k},\ldots,\varepsilon_{nk}) = (\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n) \text{ for infinitely many } k > n. \end{equation} The set of all universal matrices is denoted by $\mathcal U$. \end{defn} Universal matrices are connected with universal graphs as follows: \begin{thm} A countable non-directed graph $\Gamma$ is universal and homogeneous, if its incidence matrix $m_\Gamma$ is universal. \end{thm} \begin{proof} Write $\Gamma=\{x_1,x_2,x_3,\ldots\}$, and let $m_\Gamma$ be its incidence matrix defined by \ref{e:gr:INCIDENCE MATRIX}. By Theorem \ref{t:gr:U GRAPH UNIQUE}, we have to show that $\Gamma$ satisfies the extension property if and only if $m_\Gamma$ is universal. But this is obvious, since Definition \ref{e:gr:UNIV INCID MAT1} is only a reformulation of the extension property. \end{proof} To show the existence of a universal and homogeneous graph, we construct a universal incidence matrix $(\varepsilon_{ij})_{i,j=1}^\infty$ as follows: Choose an enumeration $\{w^{(1)},w^{(2)},w^{(3)},\ldots\}$ of all finite words with alphabet $\{0,1\}$, such that every finite word occurs infinitely often. Extend these finite words $w^{(i)}$ arbitrarily to infinite words $\tilde{w}^{(i)}\in \{0,1\}^{\mathbb N}$. Now define $\varepsilon_{ij}$, $ij$. This already defines an incidence matrix, such that (\ref{e:gr:UNIV INCID MAT2}) is satisfied. We thus have proved \begin{thm}\label{t:gr:U GRAPH EXISTS} There exists a countable, non-directed graph which is universal and homogeneous. By Theorem \ref{t:gr:U GRAPH UNIQUE} this graph is determined uniquely up to isomorphism. \end{thm} Since such a universal and homogeneous graph is unique (up to isometry), we simply speak of \emph{the} universal graph $\Gamma_U$. Suppose $x,y\in\Gamma_U$ are such that $(x,y)\notin \Gamma_U^{(1)}$. By the extension property, there is a point $z\in \Gamma_U$ such that both $(x,z),(z,y) \in \Gamma_U^{(1)}$. Thus the graph metric \[ d(x,y)= \min \# \text{ edges in }\gamma, \] where the min is taken over all paths which join $x$ and $y$, can only attain the values \[ d(x,y) = \begin{cases} 0 & \text{ if }x=y \\ 1 & \text{ for }(x,y)\in \Gamma^{(1)} \\ 2 & \text{ otherwise } \end{cases}. \] \subsection{Action of the group $S^\infty$ and the set of universal matrices} We denote by $\mathcal M\subseteq\{0,1\}^{\mathbb N\times\mathbb N}$ the set of all incidence matrices, equipped with the topology that inherits from the product topology on $\{0,1\}^{\mathbb N\times\mathbb N}$, and by $\mathcal U$ the subset of all universal incidence matrices. The space $\mathcal M$ is compact and metrizable, and $\mathcal U$ is a closed subset of $\mathcal M$. Let denote by $S^\infty$ the group of all permutations on the naturals $\mathbb N$. Equipped with the topology of point-wise convergence, and choosing a proper metric, for example the usual metric for point-wise convergence \[ d(g_1,g_2)= \sum 1/2^n \frac{|g_1(n)-g_2(n)|}{1+|g_1(n)-g_2(n)|}, \] $S^\infty$ is a complete separable metric space (=polish space), which is not locally compact. Moreover, \emph{this topology makes $S^\infty$ to a non-locally compact, polish group}. All finite permutations form a dense subgroup $S_\infty$ of $S^\infty$. For any $g\in S^\infty$ and infinite matrix $(a_{ij})_{i,j=1}^\infty$ we define \begin{equation}\label{e:gr:PERMUTATION OF MATRIX} T_g (a_{ij}) = g \, (a_{ij}) \, g^{-1} = (a_{g(i),g^{-1}(j)})_{i,j=1}^\infty. \end{equation} Clearly $T_g$ leaves the set $\mathcal M$ of incidence matrices invariant. Via $g\mapsto T_g$, the group $S^\infty$ (or $S_\infty$) acts on $\mathcal M$. Note that for any finite permutation $g\in S_\infty$, $T_g: \mathcal M \rightarrow \mathcal M$ is a homeomorphism, whereas for any infinite permutation it is only a Borel-automorphism. Consider a graph $\Gamma$ with incidence matrix $m_\Gamma$: Another (countable, non-directed) graph $\tilde \Gamma$ is isomorphic to $\Gamma$ if and only if \[ m_{\tilde \Gamma} = g m_{\Gamma} g^{-1} \] for some $g\in S^\infty$, or equivalently if the orbits $S^\infty m_{\Gamma}$ and $ S^\infty m_{\tilde\Gamma}$ coincide. In this sense we may regard the group $\Aut \Gamma$ of all automorphisms of $\Gamma$ as a (closed) subgroup of $S^\infty$. {\bf PROBLEM} How does the group $\Aut(\Gamma_U)$ of automorphisms of the universal graph $\Gamma_U$ look like? It is known that this group is simple (see \cite{CAM01}) Very interesting question whether this (uncountable) group has unitary representations which do not extend to the whole group $S^\infty$ As we saw $\mathcal U$ is $S^\infty$-invariant subset of $\mathcal M$. Moreover, since any two universal graphs are isomorphic, \emph{$S^\infty$ acts transitively on the set $\mathcal U$ of universal matrices}, i.e. if $m_1, m_2\in\mathcal U$, then there is a $g\in S^\infty$ such that \[ m_2= g \, m_1 \, g^{-1}. \] By the universality condition, it is clear that \emph{for any universal matrix $m$, its orbit $S^\infty m$ is dense in $\mathcal M$}. \begin{thm}\label{t:gr:UNIV MAT ARE GDELTA} The set $\mathcal U$ of all universal incidence matrices is a dense $G_\delta$-subset of $\mathcal M$. \end{thm} \begin{proof} For any finite binary word $w = (\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$, the set $ M_w = \{ (\varepsilon_{ij})_{i,j=1}^\infty \in \mathcal M : (\ref{e:gr:UNIV INCID MAT2})\text{ holds } \} $ equals \[ \bigcap_{m>n}\bigcup_{k\geq m} \{ (\varepsilon_{ij})_{i,j=1}^\infty \in \mathcal M : (\varepsilon_{1k}, \varepsilon_{2k}, \ldots, \varepsilon_{nk}) = (\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n) \} \] is a $G_\delta$ set in $\mathcal M$. Therefore, as the intersection of countably many $M_w$, the set $\mathcal U$ is also $G_\delta$. For any universal incidence matrix $m$, the orbit $S_\infty M$ is dense in $\mathcal M$. Since $\mathcal U$ is $S_{\infty}$-invariant, this completes the proof of the theorem. \end{proof} \subsection{Random graphs} Now we will define the probability measures on the set of all countable graphs and in particular give a probabilistic proof of the existence of the universal graph $\Gamma_U$. That fact that the simplest such probability measures (independent entries) gives with probability one the universal graph is due to P. Erd\"os and A. R\'enyi (\cite {ERD01} see also \cite{CAM01}). This proof will also imply the existence $S^{\infty}$-invariant measures which are concentrated on the set $\mathcal U$ of universal incidence matrices. We first give an intuitive description. Starting with a single point (one-point graph), we successively define random graphs $\Gamma_n$, $n=1,2,3, \ldots$ in the following manner: To a given $n$-point graph $\Gamma_n=\{x_1,x_2,\ldots,x_n\}$ we add a $n+1$-th point $x_{n+1}$ and independently set edges in $\Gamma_{n+1}=\Gamma_n\cup \{x_{n+1}\}$ between the new point $x_n$ and the old points $x\in \Gamma_n$ according to \begin{align*} \text{Prob}[(x_{n+1},x_m)\in \Gamma_{n+1}] & = p \\ \text{Prob}[(x_{n+1}, x_m)\notin \Gamma_{n+1}] &= 1-p, \end{align*} where $0j$. Then, with probability one, $(\xi_{ij})_{i,j=1}^\infty$ is a universal incidence matrix. \end{thm} \begin{proof} We only have to show that, with probability one, every binary word $(\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)\in\{0,1\}^n$ occurs infinitely often: \[ P[(\xi_{11},\xi_{2k},\ldots,\xi_{nk})= (\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n) \text{ for infinitely many } k>n] = 1. \] But this is evident since all the $\xi_{ij}$, $in$ \[ 0< P[(\xi_{1k},\xi_{2k},\ldots,\xi_{nk})= (\varepsilon_1,\varepsilon_2,\ldots,\varepsilon_n)]<1, \] which follows from $00$. A mapping $\iota: M_1\rightarrow M_2$ is said to be an {\it $\varepsilon$-isometry}, if \[ \| d_1(x,y)-d_2(x,y)\| \leq \varepsilon, \qquad x,y \in M_1. \] \end{defn} \begin{defn} Suppose $\varepsilon \geq 0$. A metric space $(M,d)$ is said to have the {\it $\varepsilon$-extension property}, if the following holds: Given any finite metric space $(F,d_F)$, and a one-point extension $(F', d_{F'})$ of $(F,d_F)$. If there is an isometric mapping $\iota: F \rightarrow M$, then $\iota$ can be extended to an $\varepsilon$-isometry $\iota': F'\rightarrow M$, i.e. the following diagram commutes: \begin{equation*} \begin{CD} F @>{\iota \quad \text{(isometry)}}>> M \\ @V{id}VV @V{id}VV \\ F' @>{\iota' \quad (\varepsilon-\text{isometry})}>> M \end{CD}. \end{equation*} If $\varepsilon=0$, we simply speak of the {\it extension property}. \end{defn} In other words, $(M,d)$ satisfies the $\varepsilon$-extension property if and only if to any finite subspace $F\subseteq M$, and any (exterior) one-point metric extension $(F'=F\cup\{a\},d_{F'})$ of $F$, there exists a point $a_\varepsilon \in M$ such that \[ |d(a_\varepsilon,x)-d_{F'}(a,x)| \leq \varepsilon, \qquad x\in F. \] The extension property allows us to extend locally defined isometries to global isometries via a so-called \emph{back and forth} argument: \begin{lem}\label{l:BACK AND FORTH} Suppose $(M,d)$, $(\tilde{M},\tilde{d})$ are polish spaces which have the extension property, $F\subseteq M$ finite. Then any isometric mapping $\iota: F\rightarrow \tilde{M}$ can be extended to a bijective isometry $\iota': M\rightarrow \tilde{M}$. \end{lem} \begin{proof} Choose countable dense subsets $\{x_1,x_2,\ldots\}\subseteq M$ and $\{y_1,y_2,\ldots\}\subseteq \tilde{M}$. Denote $F_1=F$, $G_1=\iota (F_1)$, and $\iota_1 = \iota : F_1 \rightarrow G_1$. Define $G_2=G_1\cup \{y_1\}$. By the extension property, $\iota_1^{-1}:G_1\rightarrow F_1$ extends to an isometry $\iota_2^{-1}: G_2\rightarrow F_2$ onto a subset $F_2\supseteq F_1$. Now define $F_3= F_2\cup\{x_1\}$. Again there is an isometry $\iota_3:F_3\rightarrow G_3$ onto a subset $G_3\supseteq G_2$. Take $G_4=G_3\cup \{y_2\}$. Continuing in the same manner as above, we can construct inductively subsets \[ F_1\subseteq F_2 \subseteq \cdots \subseteq F_n \subseteq \cdots \subseteq M \] with \[ F_n\supseteq \{x_k : 1\leq k \leq \frac{n-1}{2}\}, \] subsets \[ G_1\subseteq G_2 \subseteq \cdots \subseteq G_n \subseteq \cdots \subseteq \tilde{M} \] satisfying \[ G_n\supseteq \{y_k: 1\leq k \leq \frac{n}{2}\}, \] and isometric bijections $\iota_n: F_n\rightarrow G_n$, \[ \iota=\iota_1\subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq \cdots \] The mapping $\iota_\infty=\bigcup_{n=1}^\infty \iota_n$ maps $F_\infty= \bigcup_{n=1}^\infty F_n $ isometrically onto $G_\infty= \bigcup_{n=1}^\infty G_n$. Since $F_\infty$ and $G_\infty$ are dense, and since the metrics on $M$ and $\tilde{M}$ are complete we may extend $\iota_\infty$ to an bijective isometry $\iota':M\rightarrow \tilde{M}$. \end{proof} \begin{thm}\label{t:U SPACE IS UNIQUE} A polish space is a Urysohn space if and only if it has the extension property. Two Urysohn spaces are isometrically isomorphic. \end{thm} \begin{proof} A Urysohn space $(M,d)$ has the finite extension property: By universality there is an isometry $\kappa: F_2\rightarrow M$. Define $i:\kappa(F_1)\rightarrow\iota(M_1)$, $i = \iota\circ\kappa^{-1}$. Now, choose an automorphism $J:M\rightarrow M$ which extends $i$. The mapping $J\circ\kappa: F_2\rightarrow M$ is an extension of $\iota$. On the other hand, if $(M,d)$ has the extension property, then $(M,d)$ is obviously universal. Moreover, if $\iota: F_1\rightarrow F_2$ is an isometry between finite subspaces of $M$, then Lemma \ref{l:BACK AND FORTH} (setting $M=\tilde{M}$) shows the existence of an automorphism $\iota':M\rightarrow M$ which extends $\iota$. The uniqueness of two Urysohn spaces $(M,d)$,$(\tilde M,\tilde d)$ is now obvious: Choose any two points $x_1\in M$, $x_2 \in \tilde M$ and consider the isometry $\iota: x_1\mapsto x_2$. Since both spaces posses the extension property, Lemma \ref{l:BACK AND FORTH} allows us to extend $\iota$ to an isomorphism $\iota':M\rightarrow \tilde M$. \end{proof} \begin{rem} The existence of a polish space which is Urysohn is shown in Section \ref{s:U SPACE EXISTENCE}. Since such a space is unique up to isometry, we will simply speak of \emph{the} Urysohn space $(\mathfrak U,d)$. \end{rem} Note that if a polish space $(M,d)$ satisfies the extension property, then it is also universal in the category of polish spaces, i.e. every polish space $(P,d)$ can be embedded isometrically into $M$: Choose a countable dense subset $\{x_1,x_2,\ldots\}\subseteq M'$, and denote $F_n = \{x_1,\ldots, x_n\}$. There exist exists isometric mappings $\iota_n: F_n\rightarrow M$, \[ \iota_1\subseteq \iota_2 \subseteq \cdots \subseteq \iota_n \subseteq \cdots \] The mapping $\iota_\infty=\bigcup_{n=1}^\infty \iota_n$ maps $F_\infty= \bigcup_{n=1}^\infty F_n $ isometrically into $M$. Since $F_\infty$ is dense in $P$, and since the metric on $M$ is are complete, we may extend $\iota_\infty$ to an isometry $\iota:P\rightarrow M$. \begin{lem}\label{l:EPSILON EXTENSION} Suppose a complete metric space $(M,d)$ satisfies the $\varepsilon$-extension property for all $\varepsilon>0$. Then $(M,d)$ has the extension property for compact metric spaces: Given any compact metric space $(C,d_C)$, and any one-point (or polish) extension $(C',d_{C'})$ of $(C,d_C)$. If there is an isometric mapping $\iota: C \rightarrow M$, then $\iota$ can be extended to an isometry $\iota': C' \rightarrow M$, i.e. the following diagram commutes: \begin{equation*} \begin{CD} C @>{\iota \quad \text{(isometry)}}>> M \\ @V{id}VV @V{id}VV \\ C' @>{\iota' \quad (\varepsilon-\text{isometry})}>> M \end{CD} \end{equation*} \end{lem} \begin{proof} First of all, note that for arbitrary $\varepsilon>0$ the $\varepsilon$-extension property holds also for compact metric spaces: Given any compact metric space $(C,d_C)$, one-point extension $(C'=C\cup\{a\},d_{C'})$, and isometry $\iota: C\rightarrow M$. Because $C$ is compact, we may choose a finite set $F\subseteq C$ such that \[ \min_{y\in F} d(\iota x,\iota y) \leq \varepsilon/2, \qquad x\in C. \] By the assumption on $M$, there exists an $\varepsilon/2$-extension of the restriction of $\iota$ to $F$, which maps $a$ to $x_a\in M$, say. Now the function \[ \iota': C\cup\{a\}\rightarrow M, \begin{cases} \iota'=\iota & \text{on } C \\ a\mapsto x_a & \end{cases} \] is an $\varepsilon$-extension of $\iota:C\rightarrow M$, as one easily can verify. To show the extension property, we have to find a point $\alpha\in M$ such that \begin{equation}\label{e:LOC01} d(\alpha,\iota(x))=d_{C'}(a,x), \qquad x\in C. \end{equation} Choose $\varepsilon_n$, such that $\sum_{n=0}^\infty \varepsilon_n < \infty$. We will define inductively a sequence of points $x_n\in M$, $n=0,1,2,\ldots$, such that \begin{equation}\label{e:LOC02} |d(x_n,\iota(x))-d_{C'}(a,x)|\leq \varepsilon_n, \qquad x\in C, \end{equation} and such that the sequence $(x_n)$ is Cauchy in $M$. Then, since $M$ is complete, there exists a limit $\alpha$ which certainly satisfies (\ref{e:LOC01}). Since $M$ satisfies the $\varepsilon$-extension property for $\varepsilon = \varepsilon_0$, we can find a point $x_0\in M$ which satisfies (\ref{e:LOC02}) with $n=0$. Define the other $x_n$, $n\geq 1$, by applying the following induction step: Given a point $x_n$ which satisfies (\ref{e:LOC02}). Define an (exterior) one-point extension $(C\cup\{x_n,b\},d')$ of $(C\cup\{x_0\},d)$ by: \begin{align*} d'(x,y) &= d(x,y) \qquad x,y\in C\cup\{x_n\} \\ d'(x,b) &= d_{C'}(x,a) \qquad x\in C \\ d'(x_n,b) &= \varepsilon_n \end{align*} In fact, by (\ref{e:LOC02}), $d'$ satisfies the triangular inequality (if in addition $\varepsilon_n \leq \inf_{x\in C} d_{C'}(x,a)$, which we certainly may assume) as one can easily verify. Since $M$ satisfies the $\varepsilon$-extension property for $\varepsilon = \varepsilon_{n+1}$, we can find a point $x_{n+1}\in M$ such that \[ |d(x_{n+1},\iota(x))-d_{C'}(a,x)|\leq \varepsilon_{n+1}, \qquad x\in C, \] and \[ d(x_n,x_{n+1}) \leq d'(x_n,b) + \varepsilon_{n+1} = \varepsilon_n + \varepsilon_{n+1}. \] By construction, \ref{e:LOC02} is satisfied, and since $\sum \varepsilon_n <\infty$, the latter inequality shows that $(x_n)$ is a Cauchy sequence, which completes the proof. \end{proof} As an immediate consequence of Lemma \ref{l:EPSILON EXTENSION}, any polish space $(M,d)$ which satisfies the extension property (for finite metric spaces ) also satisfies the extension property for compact metric spaces. Repeating the proof of Lemma \ref{l:BACK AND FORTH} verbatim we may conclude: \begin{lem}\label{l:u:BACK AND FORTH COMP} Suppose $(M,d)$, $(\tilde{M},\tilde{d})$ are polish spaces which have the extension property, $C\subseteq M$ compact. Then any isometric mapping $\iota: C\rightarrow \tilde{M}$ can be extended to a bijective isometry $\iota': M\rightarrow \tilde{M}$. \end{lem} In particular, this shows that the Urysohn space is homogeneous with respect to its compact subspaces. Hence the Urysohn space $\mathcal U$ is a ``good'' universal object in the category of all compact metric spaces: every compact metric space $(C,d_C)$ can be embedded isometrically into $\mathcal U$, and this embedding is unique up to isometry, i.e. if $\iota_1:C \rightarrow U$, $\iota_2: C \rightarrow U$ are two such isometries, then there exists an automorphism $J:\mathcal U\rightarrow \mathcal U$ such that \[ \iota_1 = J \circ \iota_2. \] Lemma \ref{l:u:BACK AND FORTH COMP} is not true assuming $C$ to be closed, even countable (see \cite{BOG01}, \cite{HUHU01}). The following Theorem which will be important for our construction of the Urysohn space (See subsection \ref{s:U SPACE EXISTENCE}): \begin{thm} A polish space is Urysohn if and only if it satisfies the $\varepsilon$-extension property for every $\varepsilon>0$. \end{thm} \begin{proof} Combine Lemma \ref{l:EPSILON EXTENSION} and Theorem \ref{t:U SPACE IS UNIQUE}. \end{proof} \subsection{Construction, Universal Matrices} \label{s:U SPACE EXISTENCE} Before show the existence of a Urysohn space, we need some preparations. Suppose $(M,d)$ is an infinite polish space. Choose a countable dense subset $D=\{x_1, x_2, x_3, \ldots\}$ and define a matrix $r=(r_{ij})_{i,j=1}^\infty$ by \begin{equation} \label{e:DIST MATRIX} r_{i,j}= d(x_i,x_j). \end{equation} Any matrix obtained in such a way is called a {\it (infinite) distance matrix}. The set of all infinite distance matrices is denoted by $\mathcal{R}$. We will consider $\mathcal{R}$ as topological space equipped with the topology that inherits from the product topology on $\mathbb R^{\mathbb N \times \mathbb N}$. $\mathcal R$ is a closed convex cone in $\mathbb R^{\mathbb N\times\mathbb N}$, in particular it is a polish space. Similarly we say that a finite matrix $(r_{i,j})_{i,j=1}^n$ is a {\it (finite) distance matrix}, if there exists a finite metric space $(\{x_1, x_2,\ldots, x_n\}, d)$ such that (\ref{e:DIST MATRIX}) holds. The set of all $n$-dimensional distance matrices, equipped with the product topology, is denoted by $\mathcal{R}_n$. If we define a (continuous) projection $\pi_n:\mathcal R_{n+1}\rightarrow \mathcal R_n$ by \[ \pi_n (r_{ij})_{i,j=1}^{n+1}=(r_{ij})_{i,j=1}^n, \] then we can regard $\mathcal R$ as the inverse limit of the cones $\mathcal R_n$: \[ \mathbb R^+ \stackrel{\pi_1}\leftarrow \mathcal R_2 \stackrel{\pi_2}\leftarrow \cdots \stackrel{\pi_{n-1}}\leftarrow \mathcal R_n \stackrel{\pi_{n}}\leftarrow \mathcal R_{n+1} \stackrel{\pi_{n+1}}\leftarrow \cdots \] Given a $n$-dimensional distance matrix $r_n=(r_{ij})_{i,j=1}^n$, which corresponds to $F=(\{x_1,\ldots,x_n\},d)$. A vector $b=(b_1,\ldots,b_n)$ is called {\it admissible}, if the matrix \[ r_n^b = \begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n} & b_1 \\ r_{21} & r_{22} & \cdots & r_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ r_{n1} & r_{n2} & \cdots & r_{nn} & b_n \\ b_1 & b_2 & \cdots & b_n & 0 \end{pmatrix} \] is also a distance matrix. In other words, $b$ is admissible if there exists a one-point extension $(F\cup\{x\},d')$ of $(F,d)$, such that \[ d'(x,x_i)=b_i, \qquad i=1,\ldots,n. \] The set of all admissible vectors is then denoted by $\Adm(r_n)$. It determines all one-point extensions of $(F,d)$ up to isomorphism. Note that \begin{equation}\label{e:ADMISSIBLE CONE} \Adm(r_n)= \{ (b_i)_{i=1}^n\in\mathbb R^n : b_i-b_j \leq r_{ij} \leq b_i+b_j \}, \end{equation} hence $\Adm(r_n)$ is a closed convex cone $\subseteq \mathbb{R}^n$. \begin{lem}\label{l:ADMISSIBLE CONES} Suppose $M=(\{x_1,x_2,x_3,\ldots\},d)$ is countable metric space, and consider the subspaces $F_n=(\{x_1,\ldots,x_n\},d)$, with $r_n=(d(x_i,x_j))_{i,j=1}^n$ as their corresponding distance matrices. Then \[ \mathbb R^+ \stackrel{\pi_1}\leftarrow \Adm(r_2) \stackrel{\pi_2}\leftarrow \cdots \stackrel{\pi_{n-1}}\leftarrow \Adm(r_n) \stackrel{\pi_{n}}\leftarrow \Adm(r_{n+1}) \stackrel{\pi_{n+1}}\leftarrow \cdots, \] where $\pi_n:\mathbb R^{n+1}\rightarrow \mathbb R^n$ is the projection onto the first $n$ coordinates. \end{lem} \begin{proof} It is clear that $\pi_{n+1}\Adm(r_{n+1}) \subseteq \Adm(r_n)$. To prove the opposite inclusion, it suffices to show that to any two vectors $a,b\in\Adm(r_n)$ we can construct a two-point extension $M=(F_n\cup\{y_a,y_b\},d)$ of $F_n$ with $d(x_i,y_a)= a_i$ and $d(x_i,y_b)= b_i$, $i=1,\ldots, n$. The only distance left to choose is $\alpha=d(y_a,y_b)$. The validity of the triangular inequality for $d$ is equivalent to \[ |a_i-b_i|\leq \alpha \leq a_i+b_i, \qquad 1\leq i \leq n, \] which is only possible if \[ \max_{1\leq i \leq n} |a_i-b_i| \leq \min_{1\leq i \leq n} a_i + b_i. \] But the latter inequality is true since both vectors $a$ and $b$ are admissible: There exists a one-point extension $(F_n \cup\{z_a\},d_a)$ of $F_n$ with \[ d_a(z_a,x_i)= a_i, \qquad 1\leq i \leq n, \] and a one-point extension $(F_n \cup\{z_b\},d_b)$ of $F_n$ with \[ d_b(z_b,x_i)= b_i, \qquad 1\leq i \leq n. \] Now, using the triangular inequality for both metrics, we have \[ \begin{split} a_i-b_i & = d_a(z_a,x_i) - d_b(z_b,x_i) \leq d_a(z_a,x_j) + d(x_i,x_j) - d_b(z_b,x_i) \leq\\ &\leq d_a(z_a,x_j) + d_b(z_b,x_j) = a_j + b_j. \end{split} \] Since $i$ and $j$ where arbitrary, this implies the desired inequality. \end{proof} \emph{Remark.} The above lemma shows that the cones $\Adm(r_n)$ are consistent under projections. \emph{They are also consistent under permutations:} If $g$ is any permutation on the set $\{1,2,\ldots n\}$ then we have \[ g\Adm(r_n) = \Adm(g r_n g^{-1}), \] where for vectors $x=(x_1,x_2,\ldots,x_n)$, its permutation $gx$ is defined by $gx=(x_{g(1)}, x_{g(2)}, \ldots, x_{g(n)})$. \begin{defn}\label{d:U MATRIX} A distance matrix $r=(r_{ij})_{i,j=1}^\infty$ is said to be %\begin{itemize} \emph{universal}, if for every $n\in\mathbb N$ \begin{equation}\label{e:U MATRIX} \text{closure } \{ (r_{1k},r_{2k},\ldots,r_{nk}) : k= n, n+1, \ldots \} = \Adm((r_{ij})_{i,j=1}^n). \end{equation} It is called \emph{weakly universal}, if $S_\infty r$ is dense in $\mathcal R$. %\end{itemize} The set of all universal matrices is denoted by $\mathcal M$. \end{defn} Universal matrices are connected with Urysohn spaces: \begin{thm}\label{t:U MATRIX U PROPERTY} Suppose $(M,d)$ is a polish space, $(x_n)_{n=1}^\infty$ a dense sequence. The matrix $r=(d(x_i,x_j))_{i,j=1}^\infty$ is universal if and only if $M$ is Urysohn. \end{thm} \begin{proof} Suppose $M$ is an Urysohn space. Fix $n\in\mathbb N$, $r_n = (d(x_i,x_j))_{i,j=1}^n$ and choose an admissible vector $(a_1,a_2,\ldots,a_n) \in \Adm(r_n)$. By the extension property, there is an $x\in M$ such that \[ d(x,x_i)= a_i, \qquad i=1,2,\ldots ,n. \] Since the $x_k$ are dense in $M$, the property (\ref{e:U MATRIX}) is evident. Conversely, suppose the distance matrix $(d(x_i,x_j))$ is universal. Choose a finite subset $F=\{y_1, y_2, \ldots, y_n\}\subseteq M$, and an admissible vector $(a_1,a_2,\ldots, a_n) \in \Adm(r_n)$, where $r_n= (d(y_i,y_j))_{i,j=1}^n$. Fix $\varepsilon>0$. Since the $x_k$ are dense, and since (\ref{e:U MATRIX}) holds, there are points $x_{k_1},\ldots, x_{k_n}$ and $x=x_{k_{n+1}}$ such that \[ |x_{k_i}-y_i|<\varepsilon/2, \qquad i=1,2,\ldots,n \] and \[ |d(x,x_{k_i})-a_i|<\varepsilon/2, \qquad i=1,2, \ldots, n. \] Therefore $|d(x,y_i)-a_i|<\varepsilon$, $i = 1,\ldots, n$, which proves the $\varepsilon$-extension property of $M$. Since $\varepsilon>0$ was chosen arbitrarily, we can conclude by Lemma \ref{l:EPSILON EXTENSION} that $M$ has the extension property, hence it is a universal and homogeneous space. \end{proof} It is not difficult to show that \emph{the distance matrix $r=(d(x_i,x_j))_{i,j=1}^\infty$ is weakly universal, if and only if $(M,d)$ is weakly universal in the following sense: To any finite metric space $(F,d_F)$, and any $\varepsilon>0$, there exists an $\varepsilon$-isometry $\iota$ which maps $F$ into $M$.} Thus every universal matrix is also weakly universal. The converse is not true: there exists weakly universal matrices (spaces), which are not universal matrices (spaces, resp.). For example consider a sequence of metric spaces \[ (F_1,d_1),(F_2,d_2), (F_3,d_3), \ldots, \] such that their corresponding distance matrices \[ r_1, r_2, r_3, \ldots \] enumerate all rational distance matrices of all dimensions. Now consider the disjoint sum $(M,d)$ of the spaces $(F_i, d_i)$, i.e. $M=\bigcup_i F_i$ and \[ d(x,y)= \begin{cases} d_i(x,y) & \text{for }x,y\in F_i \\ \frac{\diam(F_i)+\diam(F_j)}{2} & \text{for } x\in F_i, y\in F_j \end{cases}, \] where $\diam(F_i) = \max_{x,y\in F_i} d_i(x,y)$. The space $(M,d)$ is complete, since it consists of isolated points only, separable, by construction weakly universal but not every finite metric space can be embedded into $M$. Before we can start with the construction of the Urysohn space, we need another auxiliary lemma, which proof we leave to the reader. \begin{lem}\label{l:LIFT DENSE SEQU CONES} Suppose $A_n$,$A_m$ are convex cones in $\mathbb R^n$, $\mathbb R^m$ respectively ($n>m$), such that $\pi A_n= A_m$, where $\pi:\mathbb R^n\rightarrow \mathbb R^m$ is the projection onto the first $m$ coordinates. If $(a_i)_{i=1}^\infty$ is a sequence dense in $A_m$, then we can find vectors $(a_i')_{i=1}^\infty$ dense in $A_n$ such that \[ \pi a_i' = a_i, \qquad i\in\mathbb N. \] \end{lem} \emph{Now we are able to construct a Urysohn space, or equivalently a universal matrix}: To do so, we define a metric $d$ on the set of naturals $\mathbb N$ as follows. Choose a sequence $(a_n^{(1)})_{n=2}^\infty$ dense in $\mathbb R_+$ and define \[ d(1,n) = a_n^{(1)}, \qquad i=2,3,\ldots \] Note that $d$ already defines a metric on the two-point set $\{1,2\}$. Set $r_1=(0)$, and let $r_2$ be the distance matrix which corresponds to the two-point space $(\{1,2\},d)$. Since the projection $\pi:\mathbb R^2\rightarrow \mathbb R$, $(x_1,x_2)\rightarrow x_1$ maps $\Adm(r_2)$ onto $\Adm(r_1)=\mathbb R_+$, Lemma \ref{l:LIFT DENSE SEQU CONES} shows that there is a sequence of numbers $(a_n^{(2)})_{n=3}^\infty$ such that \[ \Adm(r_2)= \text{closure }\{\begin{pmatrix}a_n^{(1)} \\a_n^{(2)}\end{pmatrix}: n\ge 3\}. \] Define \[ d(2,n)= a_n^{(2)}, \qquad n=3,4,\ldots \] This defines already a metric on the three-point set $\{1,2,3\}$. Now let $r_3$ be the distance matrix corresponding to $(\{1,2,3\},d)$. Again, we can find a sequence of non-negative numbers $(a_n^{(3)})_{n=4}^\infty$ such that \[ \Adm(r_3)= \text{closure }\{\begin{pmatrix}a_n^{(1)} \\a_n^{(2)} \\ a_n^{(3)}\end{pmatrix}: i\ge 4\}. \] Define \[ d(3,n)= a_n^{(2)}, \qquad n \ge 4. \] Continuing in this manner, we obtain a metric $d$ on $\mathbb N$ such that by construction the matrix $(d(i,j))_{i,j=1}^\infty$ is universal. Therefore the completion of $(\mathbb N, d)$ is a Urysohn space. We have proved the main theorem of this section: \begin{thm}[Urysohn]\label{t:U SPACE EXISTENCE} There exists a polish space $(\mathfrak U,d)$ which is universal and homogeneous. By Theorem \ref{t:U SPACE IS UNIQUE} this space is determined uniquely up to isomorphism. \end{thm} {\it Remark.} For $\alpha>0$, restricting ourselves to bounded distance matrices $r\in [0,\alpha]^{\mathbb N\times \mathbb N}$, one similarly can construct a homogeneous polish space $\mathfrak U_\alpha$ of diameter $\alpha$ which is universal in the following sense: {\it Every polish space of diameter $\leq \alpha$ can be embedded isometrically into $\mathfrak U_\alpha$.} Such a space is also unique up to isometric equivalence. \subsection{Some Properties of the Urysohn space} \label{s:PROPERTIES URYSOHN} We now consider topological properties of the Urysohn space. \begin{thm}\label{t:u:COMPACTA CONTRACTIBLE} Any continuous map $f:C\rightarrow \mathfrak U$ from a compact metric space $(C,d_C)$ into the Urysohn space $(\mathfrak U,d)$ is contractible (=homotopic to the constant map). \end{thm} \begin{proof} Consider the image $f(C)$ as a subspace of $\mathfrak U$. This is a compact metric space and we therefore can find a isometric embedding $\iota:f(C)\rightarrow B$ into a separable Banach space $(B,\|\,.\,\|)$ (as was shown at the beginning of this section). By the extension property, the isometry $\iota^{-1}:\iota(f(C))\rightarrow C$ can be extended to an isometry $J: B\rightarrow \mathfrak U$: \begin{equation*} \begin{CD} (C,d_C) @>{f}>> (\mathfrak U,d) \\ @V{g=\iota\circ f}VV @V{id}VV \\ (B,\|\,.\,\|) @>{J}>> (\mathfrak U,d) \end{CD} \end{equation*} Since the mapping $g:C\rightarrow B$ is contractible, $f$ is also contractible. \end{proof} \begin{thm}\label{t:U SPACE HOMOTOPY TRIVIAL} The Urysohn space $(\mathfrak U,d)$ is path-wise connected. Moreover all homotopy groups $\pi_n$ (and therefore all homology groups) are trivial. \end{thm} \begin{proof} That $\mathfrak U$ is path-wise connected is an immediate consequence of the extension property: The mapping which maps two different numbers $a,b\in\mathbb R$ to two different points $x,y\in \mathfrak U$ is an isometry, provided we have chosen the proper norm on $\mathbb R$, and can therefore be extended to an isometric embedding of the whole interval $[a,b]$ into $\mathfrak U$. By Theorem \ref{t:u:COMPACTA CONTRACTIBLE}, any continuous mapping $f:S^{n}\rightarrow \mathfrak U$ from the $n$-dimensional sphere into $\mathfrak U$ is contractible, hence all homotopy groups of $U$ are trivial. \end{proof} {\bf PROBLEM} Is Urysohn space $\mathfrak U$ contractible or not? Consider the group $\Aut(\mathfrak U)$ of isometries of the Urysohn space, equipped with the topology of pointwise convergence. In \cite{USP01}, the author shows that $\Aut(\mathfrak U)$ is a universal topological group with a countable base, i.e. every Hausdorff topological group with a countable base is isomorphic to a subgroup of $\Aut(\mathfrak U)$. Apart from that, not very much is known about this group. {\bf PROBLEM} To describe algebraic or topological properties of the Isometry Group $\Aut(\mathfrak U)$ of the Urysohn space $\mathfrak U$. We continue with miscellaneous considerations about the Urysohn space. \begin{thm}\label{t:u:UTIMESU} Consider the product $\mathfrak U^2= \mathfrak U\times \mathfrak U$ equipped with the maximum metric $d_\infty((x,y),(x',y'))= \max \{ d(x,x'), d(y,y')\}$. The product $\mathfrak U^2$ is separable and universal, but not isometrically isomorphic to $\mathfrak U$ \end{thm} \begin{proof} We show that $(\mathfrak U^2,d_\infty)$ does not satisfy the extension property: Choose a subspace $F_1=\{x_1,x_2,x_3\}\subseteq \mathfrak U$ with distance matrix \[ r_{F_1}= \begin{pmatrix} 0 & 1 & 1/4 \\ 1 & 0 & 1 \\ 1/4 & 1 & 0 \end{pmatrix}. \] and a subspace $F_2=\{y_1,y_2,y_3\}\subseteq \mathfrak U$ with distance matrix \[ r_{F_2}= \begin{pmatrix} 0 & 1/4 & 1 \\ 1/4 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}. \] Let $F\subseteq \mathfrak U^2$ be the subspace which consists of the points $(x_i,y_i)$, $i=1,2,3$. All edges of this triangle have length one, i.e. the distance matrix of $F$ is \[ r_F= \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}. \] The vector $(1/2,1/2,1)\in\Adm(r_F)$, but, by equation (\ref{e:ADMISSIBLE CONE}), any vector $(b_1,b_2,b_3)\in \Adm(r_{F_j})$, $j=1,2$, with $b_j\leq 1/2$ must have $b_3 < 1$. Thus there is no point $(a,b)\in \mathfrak U^2$ such that \[ (d((a,b),(x_i,y_i)))_{i=1}^3 = (1/2,1/2,1). \] \end{proof} \begin{rem} The same argument as in the proof of Theorem \ref{t:u:UTIMESU} also works out for the product $\mathfrak U\times [0,1]^2$ (equipped with the maximum metric). Hence $\mathfrak U\times [0,1]^2$ and therefore $\mathfrak U\times [0,1]$ (also equipped with the maximum metric) is not isometrically isomorphic to $\mathfrak U$. \end{rem} \emph{For any $\alpha >0$, $(\mathfrak U,\alpha d)$ also has the extension property and is therefore isometrically isomorphic to $(\mathfrak U,d)$}: Suppose $\iota: C\rightarrow \mathfrak U$ is an isometric embedding of a compact space $(C,d_C)$ into $(\mathfrak U,\alpha d)$, and suppose $(C',d_C')$ is a one-point extension of $(C,d_C)$. By \[ \alpha d(\iota x,\iota y) = d_C(x,y), \qquad x,y\in C \] the same $\iota$ embeds $(C, \alpha^{-1}d_C)$ isometrically into $(\mathfrak U,d)$. We thus can find an isometry $\iota':(C',\alpha^{-1}d_{C'}) \rightarrow (\mathfrak U,d)$ which extends $\iota$. By the same argument as before, $\iota'$ is also an isometric embedding of $(C',d_{C'})$ into $(\mathfrak U,\alpha d)$. \subsection{The set $\mathcal U$ of universal matrices} As for incidence matrices in Section \ref{s:UNIVERSAL AND RANDOM GRAPHS}, the group $S^\infty$ of permutations on $\mathbb N$ acts via formula (\ref{e:gr:PERMUTATION OF MATRIX}) also on the cone of all distance matrices. Unlike to the case of graphs may not regard $\Aut(\mathfrak U)$ as a subgroup of $S^\infty$. \begin{thm}\label{t:U MATR DENSE GDELTA} The set $\mathcal U$ of all universal distance matrices is $S_\infty$-invariant, i.e. $ g\mathcal M g^{-1} = \mathcal M$ for every $g\in S_\infty$. Moreover, it is a dense $G_\delta$-subset of $\mathcal R$. \end{thm} \begin{proof} >From the remark which follows Lemma \ref{l:ADMISSIBLE CONES} it is obvious that a distance matrix $r=(r_{ij})_{i,j=1}^\infty$ is universal if and only if for every finite subset $\{k_1, k_2, \ldots, k_n\}\subseteq \mathbb N$, \[ \Adm((r_{k_i k_j})_{i,j=1}^n)= \text{closure } \{ (r_{k_1k}, r_{k_2k}, \ldots, r_{k_nk}) : k= n, n+1, \ldots \}. \] Thus $\mathcal M$ is $S_\infty$-invariant. By the above construction, there is at least one universal matrix $r\in\mathcal R$. Its orbit $S_\infty r$ dense in $\mathcal R$, and consists of universal matrices only. Hence $\mathcal U$ is dense in $\mathcal R$. For fixed $n,m\in \mathbb N$ and $\alpha>0$, the function $$ \varepsilon_{n,m,\alpha}: r=(r_{ij})\mapsto \sup_{a\in\Adm(\pi_n r), \|a\|\leq\alpha} \min_{nn}[\varepsilon_{n,m,\alpha}<\frac{1}{k}] $$ is therefore a $G_\delta$-set. \end{proof} We will now give a probabilistic proof of the existence of the Urysohn space in the spirit of Erd\"os Theorem \ref{t:gr:ERDOS}. This procedure will also give an idea of a random metric space. To emphasize the principle idea we only give an intuitive but not formally rigorous presentation: Starting with a single point we successively construct a random sequence $(M_n,d_n)$ of $n$-point metric spaces (or $n$-dimensional distance matrices $r_n$) , \[ (M_0,d_0)\subseteq(M_1,d_1)\subseteq (M_2,d_2) \subseteq \ldots \subseteq (M_n,d_n) \subseteq \ldots, \] as follows: to a given $n$-point metric space $M_n$ (with distance matrix $r_n\in \mathcal R_n $) we randomly add a $n+1$-th point choosing the distances between the new and the previous points (= admissible vector $\in\Adm (r_n)$) according to a certain (conditional) probability distribution $\mu_{r_n}$ (this is a probability measure on $\Adm(r_n)$). To ensure that, with probability one, the so obtained space is Urysohn (or equivalently, its distance matrix is universal), we choose the distributions $\mu_r$ as follows: On the one-dimensional admissible cone $\mathbb R^+$ we take any fixed measure $\mu_\emptyset$ which supports the whole half-line (i.e. to any open subset $B$ of $\mathbb R^+$, $\mu_\emptyset(B)>0$). Now we continue inductively via the following procedure: Suppose we had constructed all the measures $\mu_{r_n}$ for all one-dimensional distance matrices $r_n\in \mathcal R_n$ such that its support $\supp \mu_{r_n}$ is always the whole admissible cone $\Adm(r_n)$. For any $n+1$-dimensional distance matrix $r_{n+1}\in \mathcal R_{n+1}$, recall that \[ \Adm(\pi_n r_{n+1}) \stackrel{\pi_n}\leftarrow \Adm(r_{n+1}), \] where the projection is onto. Now in $\Adm(r_{n+1})$ we take any measure $\mu_{r_{n+1}}$ such that $\pi_n \mu_{r_{n+1}} = \mu_{r_n}$ and \[ \supp \mu_{r_{n+1}} = \Adm(r_{n+1}) \] Such a measure does exist, but we won't give the detailed construction here. On the cone $\mathcal R_1$ we put a probability measure $\mu_1$, $\mu_1 = \mu_\emptyset$. Using the measures $\mu_{r}$, we define probability measures $\mu_n$ on $\mathcal R_n$ via \[ \mu_n( \:.\: | \pi_{n-1} r ) = \mu_{\pi_{n-1} r} (\tilde \pi_{n-1} \:.\:), \] where $\tilde \pi_{n-1} (r_{ij})_{i,j=1}^n = (r_{1,n}, r_{2,n}, \ldots, r_{n-1,n})$. Note that $\tilde \pi_{n-1}$ maps each matrix $r\in \mathcal R_{n}$ into the the admissible cone $\Adm(\pi_{n-1} r)$, hence this definition makes sense. The so constructed family $\mu_n$ is consistent under projection, \[ \pi_m \mu_n = \mu_m, \qquad m\leq n, \] hence it defines a probability measure $\mu$ on $\mathcal R$. By construction the probability that the random distance matrix is universal equals one, thus \[ \mu(\mathcal U) = 1. \] \begin{rem} To assure that, with probability one, the random distance matrix is universal, it is certainly not necessary that the conditional distributions are consistent under projections, i.e. \[ \mu_{\pi_m r} = \pi_m \mu_r, \qquad r\in \mathcal R_n, m\leq n, \] as assumed in the discussion above (see \cite{VERSH01}). Anyway, note that the measure $\mu$ in the above construction is generically not $S_\infty$-invariant. \end{rem} At the end of this section we gather \begin{itemize} \item (cf. Theorem \ref{t:U SPACE EXISTENCE}) There exists polish space $(\mathfrak U,d)$ which is Urysohn, i.e. universal and homogeneous. This space is unique up to isometric equivalence. \item (cf. Theorem \ref{t:U SPACE HOMOTOPY TRIVIAL}) The Urysohn space $(\mathfrak U,d)$ is path-wise connected. All homotopy groups $\pi_n$ of $(\mathfrak U,d)$, and therefore all homology groups, are trivial. \item Open question: Is $(\mathfrak U,d)$ contractible? \item Open question: Find familiar spaces to which $(\mathfrak U,d)$ is homeomorphic. \item (cf. Theorem \ref{t:U MATRIX U PROPERTY}) A space is Urysohn if and only if its distance matrix of any (= some) everywhere dense countable subset is universal. \item(cf. Theorem \ref{t:U MATR DENSE GDELTA}) The set of all universal matrices is dense $G_\delta$ subset of $\mathcal R$, which is invariant under finite permutations. \end{itemize} \subsection{Random Metric Space} Here we will give a sketch of the construction of the random metric space. For this we will define a probability measure on the space of distance matrices which is concentrated on the subset of universal matrices. This construction is analogue to the same construction of the random graph but more complicate because it is not possible to use independence of entries (triangle inequality is the obstruction to that). Choose some measure $\gamma$ on the half line ${\bf R}_+$ which has full support (e.g. gaussian measure on the half line) and let entries $$r_{1,2}, \dots r_{1,n}, \dots$$ are i.i.d with distribution $\gamma$. We will define the conditional distribution of the element of distance matrix $r_{m,n}, (n > m)$ under the condition that all the elements with indices $(i,k)$ are fixed where $1 \leq i \leq m-1, 1 \leq j \leq n$ Then the conditional distribution of the element $r_{m.n}$ is uniform distribution on the interval $[a,b]$ where $$ a=\max_{i=1, \dots m-1} |r_{i,m}-r_{i,n}|; \mbox b=\min_{i=1 \dots m-1} |r_{i,m}+r_{i,n}|$$ Lemma 2.10 shows that $a \leq b$ so interval $[a,b]$ is not empty and we can by induction to define the distributions of all entries of the distance matrix. Remark that distribution of the element $r_{m,n}$ actually depends on the distribution of $r_{i,m}$ and $r_{i,n}$ for $i= 1, \dots m-1$ only. As result we had define a probability measure $\mu_{\gamma}$ on the space of distance matrices with parameter -- measure $\gamma$ on the halfline. \begin{thm} For any absolutely continuous measure $\gamma$ on the half line $\bf R$ with positive density the set of universal distance matrices has measure 1 with respect to the measure $\mu_{\gamma}$. In another word. Let $r$ is a random distance matrix with distribution $mu_{\gamma}$ in the space of all distance matrices; then a metric space which is completion of the set of naturals $\bf N$ under the distance matrix $r$ is the Urysohn space with probability 1. \end{thm} The proof uses the law of large numbers in the special situation but we will not prove the theorem here. As in the case of graphs we emphasize that the last fact is valid for very reach set of measures on the space of distance matrices, -- we gave only one simple example which is in a sense similar to the example with independent entries for the graphs. Namely, as in paragraph 1 for the case of graph, the set of probability measures on the space of distance matrices for which subset of universal matrices has a full measure is again everywhere dense $G_{\delta}$ subset of the space of all probability measures with weak topology. \bigskip ACKNOWLEDGEMENT. Author is grateful to U.~Haboeck and Yu.~Yakubovich for the help in the preparation of the manuscript. \bigskip %\bibliographystyle{amsplain} % \setlength{\baselineskip}{0.9 \baselineskip} % \bibliography{uli} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR } % \MRhref is called by the amsart/book/proc definition of \MR. \providecommand{\MRhref}[2]{% \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2} } \providecommand{\href}[2]{#2} \begin{thebibliography}{10} \bibitem{BOG01} S.~A.~Bogaty\u\i, \emph{Metrically homogeneous spaces. (russian. russian summary)}, Uspekhi Mat. Nauk \textbf{57} (2002), no.~2(344), 3--22, translation in Russian Math. Surveys 57 (2002), no. 2, 221--240. \bibitem{CAM01} P.~J.~Cameron, \emph{The random graph}, The mathematics of Paul Erd\"{o}s, II, 333--351, Algorithms Combin., 14, Springer, Berlin, 1997. \bibitem{DUG} J.~Dugundji, \emph{Topology}, Allyn and Bacon, Boston, Mass., 1966. \bibitem{ERD01} P.~Erd\"{o}s and A.~R\'enyi, \emph{Asymetric graphs}, Acta. Math. Acad. Sci. Hungar \textbf{14} (1963), 295--315. \bibitem{HUHU01} G.~E.~Huhunai\v{s}vili, \emph{On a property of {Uryson's} universal metric space.(russian)}, Dokl. Akad. Nauk SSSR (N.S.) \textbf{101} (1955), 607--610. \bibitem{KATE01} M.~Kat\v{e}tov, \emph{On universal metric spaces}, General topology and its relations to modern analysis and algebra, VI (Prague,1986), pp. 323--330, Heldermann, Berlin, 1988. \bibitem{LIND01} J.~Lindenstrauss, G.~Olsen, and Y.~Sternfeld, \emph{The {Poulsen} simplex}, Ann. Inst. Fourier (Grenoble) \textbf{28} (1978), no.~1,vi, 91--114. \bibitem{LUSK01} W.~Lusky, \emph{The {Gurarij} spaces are unique}, Arch. Math. (Basel) \textbf{27} (1976), no.~6, 627--635. \bibitem{PHELP01} R.~R.~Phelps, \emph{Lectures on {Choquet's Theorem}}, Van Nostrand Mathematical Studies, vol.~7, Van Nostrand Company, Canada, 1966. \bibitem{URY01} P.~S.~Urysohn, \emph{Sur un espace metrique universel}, Bull. Sci. Math. \textbf{51} (1927), 1--38. \bibitem{USP01} V.~V.~Uspenskij, \emph{On the group of isometries of the {Urysohn} universal metric space}, Comment. Math. Univ. Carolin. \textbf{31} (1990), no.~1, 181--182. \bibitem{VERSH01} A.~M.~Vershik, \emph{Random and universal metric spaces}, Preprint of the Erwin Schr\"odinger Institute, No. 1234; to appear in Fundamental Mathematics Today, publ. by MCCMI (Moscow), 2003. \bibitem{VERSH02} A.~M.~Vershik, \emph{Classification of measurable functions of several arguments and invariantly distributed random matrices}, Funct. Anal. Appl. \textbf{36} (2002), no.~2, 12--27 \bibitem{VERSH03} A.~M.~Vershik, \emph{Random matrix space is Urysohn space}, Dokl. Russian Acad. of Sci. \textbf{386} (2002), no.~6. \end{thebibliography} \end{document}