184. Topics in Combinatorics. Lecture, three hours; discussion, one hour. Requisites: courses 61 (or 180), 115A. Introduction to combinatorics, including several independent topics selected to illustrate various techniques to obtain combinatorial results. Gems of modern combinatorics to be showcased. May be repeated for credit. P/NP or letter grading.

Week 1: Examples illustrating combinatorics and its connection with other areas of mathematics. Basic graph theory, Eulerian graphs. Pigeon-hole principle: Few quick example, Lemma of Dirichlet, Erdos-Szekeres bound on longest increasing/decreasing subsequence. Double counting.

Week 2: Sperner lemma and fixed point theorem of Brouwer. Ramsey Theorem for graphs and set systems. Finding convex polygon among points in the plane. Upper bound for k-colored Ramsey numbers of triangle.

Week 3: Lower bound for Ramsey numbers and the power of counting. Ramsey theory for integers, theorems of Schur and van der Waerden. Turan's theorem: proof and and applications.

Week 4: Turan numbers for general graphs, theorem of Erdos-Stone. Maximum number of edges in graph with no 4-cycles and applications.

Week 5: Probabilistic methods: elementary tools; tournaments with Schutte property, i.e., every k players are beaten by somebody; 2-colorability of uniform hypergraphs; Linearity of expectation with application to sum-free subsets.

Week 6: Probabilistic methods: graphs with large girth and large chromatic number. Three famous results on finite sets: Sperner theorem and its application to Littlewood-Offord problem.

Week 7: Three famous results on finite sets: Theorem of Bollobas on set-pairs and Erdos-Ko-Rado theorem.

Week 8: Algebraic methods: Even-odd town problem, Fischer's inequality, number of lines through non-collinear set of points, 2-distance sets in R^n.

Week 9: Algebraic methods: Bound on the number of sets with restricted pairwise intersections, modular version if restricted intersection problem, counterexample to Borsuk's conjecture.

Week 10: Spectral techniques: Adjacency matrix of a graph and its eigenvalues, Eigenvalues of cliques, complete bipartite graph, complement of a graph. and a line graph. Applications: Friendship theorem. Variational definition of eigenvalues, bounds on Max Cut, chromatic and independence number, expansion of graphs using eigenvalues.