Linear Algebra in Combinatorics

In this course we shall walk through some basic ideas in linear algebra and convex geometry that have been of use in combinatorics. Topics include duality theory in linear programming, Semi-definite programming and the Lovasz Theta function. Throughout the course, combinatorial applications will be always be kept in mind, both for intuition and motivation.

As references we mention the classical papers of Lovasz [4] and Goemans [3], in addition to the text of Matousek [5], along with some other papers [2, 1].

[1]N. Alon. The shannon capacity of a union. Combinatorica, 18 (3): 301-310, Mar 1998.
[2]D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19 (2): 217-236, 1995.
[3]M. X. Goemans. Semi-definite programming in combinatorial optimization. Mathematical Programming, 79 (1- 3): 143-161, 1997.
[4]L. Lovász. On the shannon capacity of a graph. IEEE Transactions on Information theory, 25 (1): 1-7, 1979.
[5]J. Matousek and B. Gartner. Understanding and using linear programming. Springer Science & Business Media, 2007.