2 Some basic notions 2.4 ***Graphs and matrices : A little peek***2.6 ***Some questions***

2.5 Graphs as metric spaces

Let $G$ be a connected weighted graph with strictly positive edge-weights i.e., $w(e)>0$ for all $e\in E$ . or un-weighted graphs, set $w\equiv 1$ . We now shall view graphs as metric spaces. The weight/length of a path or walk $P=v_{0}\ldots v_{k}$ is $w(P):=\sum_{i=0}^{k-1}w((v_{i},v_{i+1}))$ . Define the distance between two vertices $v\neq w$ as follows :

d_{G}(v,w):=\inf\{w(P):\mbox{$P$ is a path from $v$ to $w$}\}.

Set $d_{G}(v,v)=0$ for all $v\in V$ . Show that $d_{G}(v,w)=d_{G}(w,v)$ and further $d_{G}(v,w)=0$ implies that $v=w$ .

Exercise* 2.43 (Graph metric ).

Show that $(V,d_{G})$ is a metric space.

Even if $G$ is not connected, we have that $d_{G}$ satisfies the three axioms of a metric space. Further, define the diameter of a graph as

\operatorname{diam}(G)=\max\{d_{G}(v,w):v,w\in G\}.

Given a vertex $v$ and $r>0$ , set $B_{r}(v):=\{w:d_{G}(v,w)\leq r\}$ , the ball of radius $r$ at $v$ . For un-weighted graphs show that $|B_{n}(v)|\leq\sum_{i=0}^{n}\Delta(G)^{i}.$

Exercise* 2.44.

Let $G$ be the Cayley graph of a free group generated by a finite symmetric set of generators $S=\{s_{1},-s_{1},\ldots,s_{n},-s_{n}\}.$ Compute $|B_{n}(e)|$ for all $n$ .

Exercise 2.45.

Can you compute $|B_{n}(O)|$ for $\mathbb{L}_{d}$ for $d\geq 2$ ?

For (un-weighted) graphs, let $\Pi_{n}(v)$ be the set of self-avoiding walks of length exactly $n$ from $v$ . it holds that $|\Pi_{n}(v)|\leq\Delta(G)(\Delta(G)-1)^{n}$ where $n\in\mathbb{N}$ . Thus for $\mathbb{L}^{d}$ , we have that $|\Pi_{n}(O))|\leq 2d(2d-1)^{n}$ .

Exercise* 2.46.

Is it true that there exists a $\kappa_{d}$ such that as $n\to\infty$ , we have that $|\Pi_{n}(O)|^{1/n}\to\kappa_{d}\in[0,\infty)$ ? Hint : Use that $\log|\Pi_{n}(O)|$ is sub-additive.