Sandbox:DavidKohler/Alon try 1/Variable-length graph

A variable-length graph or VLG is a graph with weighted edges. This concept allows to handle graphs which have large or infinite parts of them being paths or regular trees.

Definition

A variable-length graph is a directed graph G = (V,E) where each edge is assigned a weight -called the length of the edge- that can be any positive real number. The length of a walk in a variable-length graph is the sum of all the lengths of the edges in the walk.

Adjacency matrix of a VLG

The usual concept of adjacency matrix can be generalized to variable-length graphs by having the coefficients of the matrix be generating functions describing the various lengths of edges in play. Let G be a variable-length graph, then its adjacency matrix, denoted Z_G(z), is the matrix whose (u,v) entry is the generating function on the variable z whose z^l coefficient is the number of edges of length l from vertex u to vertex v.

Walk matrix of a VLG

When dealing simply with graphs, we can keep track of walks in the graph by looking at powers of the adjacency matrix. The equivalent for a VLG consists of adding the powers of the adjacency matrix in order to keep track of all the various ways a walk could be of a certain length. We define the walk matrix of a variable-length graph, denoted M_G(z), to be the infinite matrix sum:

$M_{G}(z)=I+Z_{G}(z)+Z_{G}^{2}(z)+\ldots$

In other words, it is the matrix whose (u,v) entry is given by:

$(M_{G}(z))_{u,v}=\sum _{k\geq 0}c_{G}(u,v;k)z^{k}$

Where c_G(u,v;k) denotes the number of walks of length k from vertex u to vertex v.

Example

• A graph can be regarded as a variable-length graph with all edge lengths to be 1. Its adjacency matrix is simply its usual adjacency matrix A_G multiplied by the variable z (since all edges have length 1), so Z_G(z) = A_G·z.
• The morse code graph is a VLG on one vertex with four self-loops called: "dit", "dah", short gap and medium gap of respective lengths 1, 3, 3, 7. The adjacency matrix of this variable-length graph is the following 1×1 matrix: Z_G(z) = (z+2z³+z⁷)

Realization of a graph as a VLG

Starting from a graph, one can realize it as a variable-length graph while suppressing some of its vertices and edges to the cost of creating more edges in the VLG. This allows for much simpler calculations when large or infinite parts of the original graphs are paths or regular trees.

Definition

Let G be a strongly connected directed graph and let W be a subset of vertices of the graph. The realization of G on the vertex set W is the variable-length graph G|_W with vertex set W containing the following edges:

• All edges between vertices in W are preserved and assigned a unit length.
• For each (directed) walk of length k in G between two vertices in W which does not contain any vertices in W except for the first and the last; we assign an edge of length k in G|_W.

Example

For example, consider the directed graph G on three vertices which is a path with adjacency matrix:

$A_{G}=\left({\begin{array}{ccc}0&1&0\\1&0&1\\0&1&0\end{array}}\right)$

Let's realize this graph as a VLG by removing the middle vertex. This is, we'll realize this on the set of vertices W = {1,3}. When removing this vertex, we obviously get an edge of length 2 joining the two remain vertices but we also have to take into account the fact that we could return to the original vertex after visiting the middle one hence creating a loop of length two at each vertex. We thus obtain the VLG with the following adjacency matrix:

$Z_{G|_{W}}(z)=\left({\begin{array}{cc}z^{2}&z^{2}\\z^{2}&z^{2}\end{array}}\right)$

Perron-Frobenius value of a VLG

We can generalize the standard Perron-Frobenius theory to the case of variable-length graphs.

Definition

Let G be a strongly connected variable-length graph, we'll denote by λ₁(G) its Perron-Frobenius value which is defined as the limit:

$\limsup _{k\rightarrow \infty }(c_{G}(u,v;k)^{1/k}$

Where c_G(u,v;k) denotes the number of walks of length k from vertex u to vertex v. Note that this limit exists and converges independently of the vertices u and v.

Properties

• When G is a finite graph, we recover the usual Perron-Frobenius eigenvalue (the largest eigenvalue of the adjacency matrix).
• Since realization as described above preserves walk counts it also preserves the Perron-Frobenius value.

Computing λ₁(G)

See Theorem 3.5.