Ari Herman, Portland State University

*Infinite random graphs*

There are many mind-blowing theorems about infinite random graphs.
We will focus on one, discovered by Erdos and Renyi in the 60's.

J. J. Peter Veerman, Portland State University

*Random walks on directed graphs*

Let V = {1,...,n} be a vertex set and S a non-negative row-stochastic matrix (ie, rows sum to 1).
V and S define a digraph G = G(V, S) and a directed graph Laplacian L as follows.
If S_{ij} > 0, there is a directed edge j→i.
The edge set E together with V define the graph.
The Laplacian is given by L = I − S.
We note also that L can be written as L = D − DS, where D is the in-degree matrix.
The graph G is the graph associated with the matrix L.

In earlier work, it was shown that the nullspace of L has a basis whose eigenvectors correspond to certain natural sets in G known as "reaches". Let A be the transpose of S and let T be the random walk on the digraph G given by the transition probabilities: Prob(i→j) = A_{ij} = S_{ij}.

In this talk, it will be proved that if T has a forward invariant probability measure p, then it satisfies Ap = p. It follows that, for every reach of G, the probability that a random walker under T starting at kϵV ends up in the exclusive part of the reach equals the kth coordinate of the eigenvector for that reach.

In earlier work, it was shown that the nullspace of L has a basis whose eigenvectors correspond to certain natural sets in G known as "reaches". Let A be the transpose of S and let T be the random walk on the digraph G given by the transition probabilities: Prob(i→j) = A

In this talk, it will be proved that if T has a forward invariant probability measure p, then it satisfies Ap = p. It follows that, for every reach of G, the probability that a random walker under T starting at kϵV ends up in the exclusive part of the reach equals the kth coordinate of the eigenvector for that reach.