Portland State University Discrete Mathematics Seminar

Winter 2016: Neuberger Hall 373, Mondays, 4:15pm–5:15pm (previous quarters)

February 16, 2016

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.

March 1, 2016

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 Sij > 0, there is a directed edge ji. The edge set E together with V define the graph. The Laplacian is given by L = IS. We note also that L can be written as L = DDS, 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(ij) = Aij = Sij.
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.