Algebraic Techniques and their use in Combinatorics

**Important information:**

*When and where:* TTH 1-2.15 LOM 215; First meeting Jan 13. Office hours: T. 2.15-4pm, DL 454.

*Prerequisites:* Linear Algebra (222, 225 or 230/231), Discrete Mathematics (244) , Some basic knowledge in probability.

*Is this course similar to 345 Spring 2014 ? *No. The course 345 is designed to cover modern combinatorics (with applications in various fields). In Spring 2014 we cover the probabilistic aspic of the theory. This year, we cover the algebraic aspect, which is very different.

*Homework:* There will be 10 sets of HWs. The HWs are posted on Thursday and due the following Thursday (except for the breaks). No late HWs.

*TA: Shingshing [shinnyih1@gmail.com]; Monday 5-7pm, lounge, 4th floor DL. *

*Presentation: *Students are expected to read advanced materials and do a presentation at the end of the course.

*Grade: *The grade will be decided on the quality of the HWs and presentations.

*Textbooks: *We will use several (unpublished) textbooks and some articles. In the first few weeks, we focus on Linear Algebraic Method (by Babai and Frankl).

Topics:

Basic algebraic notation: Linear spaces, rank, base, and dimension. Problems from design theory.

Polynomial spaces. Problems in geometry. Hilbert’s third problem. Decomposition of complete graphs.

Matrices and Graphs. Adjacency matrix and its use. Hoffman-Singleton bound. Hoffman bound on independent set and chromatic number.