Wed-Fri 11:00-12:15

SC 1103

Office Hours: By appointment.

(Please send me an email to set up a meeting).

Please give credit wherever credit is due (collaborators, online sources...).

Some of the solutions to the problems might be available online, I advise against looking them up.

Date | Topics | Reading |
---|---|---|

Lecture 1: January 18 |
Introduction to Graphs, Spectra and Random Walks, Walking on Grids and Lines. | Sariel's notes on random walks |

Lecture 2: January 20 |
Random Walks and 2SAT, Markov Chains | Sariel's notes on random walks |

Lecture 3: January 25 |
Random Walks on Graphs,Hitting time, Commute time, Cover time, Random Walks and Electrical Networks. | Sariel's notes on random walks |

Lecture 4: January 27 |
More on Cover time, Graph Connectivity, Start Graphs and Eigenvalues. | Sariel's notes on random walks |

Lecture 5: February 1 |
Erdos-Renyi Random Graphs. | Dan Spielman's notes on random graphs |

Lecture 6: February 3 |
Galton-Watson Process, Giant Component. | Dan Spielman's notes on random graphs |

Lecture 7: February 10 |
The Laplacian. | class slides |

Lecture 8: February 15 |
Extremal Eigenvalues and Eigenvectors of the Laplacian and the Adjacency Matrix. | class slides Also see Section 3.3 of These Lecture Notes |

Lecture 9: February 17 |
The Other Eigenvectors and Eigenvalues of the Laplacian. | class slides |

Lecture 10: February 22 |
Graphic Inequalities and Lowerbounds on the Second Laplacian Eigenvalue. | class slides |

Lecture 11: February 24 |
Graph Cutting and Cheeger's Inequality. | class slides Also see These Notes and These Notes |

Lecture 12: March 7 |
Relaxations, Duality and the Connection with lambda_2. | class slides Also see chapters 4 and 5 from This Book |

Lecture 13: March 9 |
The Unique Games Conjecture and SDP Duality. | class slides |

Lecture 14: March 14 |
Random Walks and Eigenvalues. | class slides |

Lecture 15: March 28 |
Pseudorandom Generators and Random Walks on Expanders. | class slides |

Lecture 16: March 30 |
Expander Graphs and Their Properties. | class slides |

Lecture 17: April 4 |
Error-Correcting Codes. | class slides |

Lecture 18: April 6 |
Expander Codes. | class slides |

Lecture 19: April 11 |
Cayley Graphs. | class slides |

Lecture 20: April 13 |
Construction of Expanders. | See These lecture notes |

Lecture 21: April 18 |
Diameter and Second Eigenvalue. | See These lecture notes |