Fall 2017

Math 206A: Combinatorial theory

Instructor: Damir Yeliussizov [damir at math ucla edu]
Lectures: MWF 3-3:50 pm, Geology 4645
Office hours: M 4-5 pm, MS 5346

The topic will be Algebraic Graph Theory. This course will cover an introduction to spectral graph theory and various related topics from algebra and algebraic/enumerative combinatorics.

Optional texts:
- A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Springer, 2012 (available here)
- B. Bollobás, Modern Graph Theory, Springer, 1999
- R. P. Stanley, Algebraic combinatorics, Springer, 2013 (available here)

Grading will be based on several problem sets. Collaboration is allowed but solutions should be written individually and not copied from anywhere.

Tentative list of topics:
- Spectral graph theory. Graph eigenvalues. Enumeration of walks. Matrix-Tree theorem. Connectivity and cuts. Random walks.
- Rings with polynomial identities via graphs. Amitsur-Levitski theorem. Weyl algebra. Capelli identities. Grassmann algebra.
- Eulerian tours. Enumeration in directed and undirected case, orientations. Interlace polynomials.
- Gessel-Viennot method. Determinants and Pfaffians.
- Tableaux, dual graphs, and symmetric functions.
- Introduction to Total Positivity.