Many of the mathematical results in this chapter arose originally from algorithmic questions, so let me briefly describe the questions and their relation to the mathematical results.
This was one motivation for the seminal paper [25]. Consider an -vertex -regular graph , with a distinguished vertex , and where for each vertex the edges at are labeled as in some way – it is not required that the labels be the same at both ends of an edge. Now consider a sequence . The sequence defines a deterministic walk on the vertices of via
is the edge at labeled .
Say i is a
traversal sequence
for if the walk visits every vertex of .
Say i is a
universal traversal sequence
if it is a traversal sequence for every graph in the set
of edge-labeled graphs with distinguished vertices.
There exists a universal traversal sequence of length as with varying arbitrarily.
Proof. It is enough to show that a uniform random sequence of that length has non-zero chance to be a universal traversal sequence. But for such a random sequence, the induced walk on a fixed is just simple random walk on the vertices of . Writing , Theorem 6.4 implies
and so inductively (cf. Chapter 2 section yyy)
Thus by taking sufficiently large that
there is non-zero chance that the induced walk on every covers before time . The crude bound means we may take .
Another motivation for the seminal paper [25] was the time-space tradeoff in algorithms for determining connectivity in graphs. Here is a highly informal presentation, illustrated by the two Mathematician graphs. The vertices are all mathematicians (living or dead). In the first graph, there is an edge between two mathematicians if they have written a joint paper; in the second, there is an edge if they have written two or more joint papers. A well known Folk Theorem asserts that the first graph has a giant component containing most famous mathematicians; a lesser known and more cynical Folk Theorem asserts that the second graph doesn’t. Suppose we actually want to answer a question of that type – specifically, take two mathematicians (say, the reader and Paul Erdos) and ask if they are in the same component of the first graph. Suppose we have a database which, given a mathematician’s name, will tell us information about their papers and in particular will list all their co-authors.
xxx continue story
Broder et al [64]
Consider the question of getting a numerical value for (up to error factor , for fixed ) for random walk on a -vertex graph. Using Theorem 6.1 it’s clear we can do this by Monte Carlo simulation in steps.
xxx technically, using s.d./mean bounded by submultiplicitivity.
Can be deterministically calculated in a polynomial (in ) number of steps?
It’s clear one can compute mean hitting times on a -step chain in polynomial time, but to set up the computation of as a hitting-time problem one has to incorporate the subset of already-visited states into the “current state”, and thus work with hitting times for a -state chain.