Let’s assume you’re walking across a cobblestone pavement laid out in an 
grid. You’re currently standing on point 
and you want to make your way to point 
while constraining yourself to moving up a step at a time, either straight up, to the left, or to the right. Assume 
how many such paths go from your starting point to your destination?
(more…)
By way of motivation, if I gave you the graph
![z1 = (0,0);
z2 = (0,2cm);
z3 = (2cm,4cm);
z4 = (2cm,2cm);
z5 = (2cm,0);
z6 = (4cm,2cm);
pickup pencircle scaled 2;
draw z[1]--z[2]--z[3]--z[4]--z[5]--cycle;
draw z[2]--z[4]--z[6];
for i=1 upto 10:
draw z[i] withcolor .1 white withpen pencircle scaled 6;
endfor](/cz/illustrender/pictures/dc001fa7169a7cc08681725dea69d120.png "z1 = (0,0);
z2 = (0,2cm);
z3 = (2cm,4cm);
z4 = (2cm,2cm);
z5 = (2cm,0);
z6 = (4cm,2cm);
pickup pencircle scaled 2;
draw z[1]--z[2]--z[3]--z[4]--z[5]--cycle;
draw z[2]--z[4]--z[6];
for i=1 upto 10:
draw z[i] withcolor .1 white withpen pencircle scaled 6;
endfor")
and asked you to identify a relationship between 
so that a graph with n vertices and 
edges is guaranteed to contain it, how would you approach this? Here’s one surprisingly simple approach:
Let 
be the set of graphs with vertices 1 through n and M edges and introduce the uniform probability 
on . Call 
a property of a random matrix if 
and 
implies 
. A property is increasing if and 
implies also.
Show that if 
and is increasing then 
. Now show that in fact 
. (at least I think this is correct).
With regards to the original problem, this inequality implies some pretty interesting and perhaps nontrivial results: e.g. if I recall correctly, there’s some basic result saying if the average valency of a graph is large enough, it must contain a triangle– this potentially offers a method of generalizing this idea for arbitrary subgraphs.
I just came across the initial lecture for a course on spectral graph theory that did a great job of illustrating how interesting the graph laplacian is. You might’ve heard of the Fiedler vector– its magical properties are what I was searching for an explanation for–, but did you know that the top two eigenvectors of planar graphs (sometimes, most of the time?) form the coordinates of nice planar embeddings? In the same vein, the bottom eigenvectors can provide good colorings. Two incredible facts that have yet to be explained.
The video lectures that inspired.me to look up spectral graph theory are pretty interesting in their own right. The first explained a simple but apparently powerful technique for edge-preserving image smoothing based on the heat equation on graphs. The second was about a seed-based technique for image segmentation based on random walks on graphs– this looks very powerful, but the lecturer is awfully boring; it may be more interesting to just peruse his publications.
Yesterday Tropp gave me three problems to work on over the summer. The first one concerns sparse approximation: there’s general interest in finding probabilistic schemes for coming up with a sparse, quantized matrix 
which approximates a given matrix 
in some sense; he gave me two papers to read on previous approaches– A Fast Random Sampling Algorithm for Sparsifying Matrices, and Fast Computations of Low-Rank Matrix Approximations– and a preprint of a result he derived which gives a bound on the approximation error for any general scheme. My job is mainly to compare and contrast the performance of these difference schemes and the attendant error bounds, to see for what schemes and properties of his bound is tighter than the others. This will be my main concern for the next couple months.
The second and third are more theoretical. One is to find a bound on the expected Ky Fan k-norm of a standard Gaussian matrix, and the other is to find a bound on the expected value of 
where 
is a DFT matrix and 
are random restrictions to 
coordinates. Sweet stuff!
