Portland State University Discrete Mathematics Seminar

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

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.

Encoding Sudoku puzzles as partially colored graphs, we

1. state and prove Akman’s Theorem regarding the associated partial chromatic polynomial,
2. count the diagonally distinct 4×4 sudoku boards, and
3. classify and enumerate the different structure types of 4×4 boards.