### UCLA

### 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.