Algebraic techniques and applications to combinatorial problems, e.g. linear and exterior algebraic methods and intersection theorems; the combinatorial Nullstellensatz and graph coloring; Stanley-Reisner rings and face numbers of polytopes and simplicial complexes; algebraic constructions in extremal combinatorics.
Every Tuesday, a new set of exercises will be handed out, which we ask be solved and handed in the following week on Tuesday in the lecture. You may discuss the problems with other students, but we ask that all students write down their solutions individually and in their own words. The solutions will be graded and generally handed back to the students one week later. You need to achieve 80% or more of the possible points to get a grade of 6.0 for the exercises; 40% of the possible points are required for a passing grade (4.0).
The final exam will take place in the last week of the semester. The total final grade will be a combination of your exercise grade and your exam grade, each counting 50%. Passing grades for both parts are required.
For PhD students there are special rules concerning credit points (KE) for the course. If your supervisor agrees, you may simply sit in on the course and obtain 2 KE. If you successfully solving the exercises, you get additional 2 KE. In order to obtain the last remaining 1 KE, you have to take and pass the final exam.
These books and papers cover most of the topics that will be discussed in the course.
Linear algebra methods in combinatorics, by L. Babai and P. Frankl, Department of Computer Science, University of Chicago, preliminary version, 1992. Combinatorial Nullstellensatz, by N. Alon, Combinatorics, Probability and Computing 8 (1999), 7-29.
Tools from higher algebra, by N. Alon, in : "Handbook of Combinatorics", R.L. Graham, M. Groetschel and L. Lovasz, eds, North Holland (1995), Chapter 32, pp. 1749-1783.
Tools from linear algebra, by Chris Godsil, in : "Handbook of Combinatorics", R.L. Graham, M. Groetschel and L. Lovasz, eds, North Holland (1995), Chapter 31.
Combinatorics and commutative algebra, by Stanley, Richard P. Second edition. Progress in Mathematics, 41. Birkhaeuser Boston, Inc., Boston, MA, 1996.
|23.9.2008||Basic examples: Graham-Pollack Theorem, Moore graphs and the Hoffman-Singelton Theorem||Exercise Set 1|
|30.9.2008||Dimension argument, Odd and Even intersecting families, 2-distance sets, non-uniform Fisher Inequality||Exercise Set 2|
|7.10.2008||L-intersecting families: Ray-Chaudhuri -- Wilson type theorems and Snevily's Conjecture||Exercise Set 3||Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems|
|14.10.2008||Extremal set theory classics: Sperner's Lemma, LYM-Inequality, Bollobas's Set-Pair Theorem. Introduction to multilinear algebra.||Exercise Set 4|
|21.10.2008||More multilinear algebra: Tensor product and exterior product, universal properties.||Exercise Set 5|
|28.10.2008||Proof of Bollobas's Theorem, skew version. Turan problems for hypergraphs, saturated hypergraphs.||Exercise Set 6|
|4.11.2008||Some basics about convex polytopes. The upper bound theorem (UBT) for convex polytopes.||Exercise Set 7|
|11.11.2008||Combinatorial nullstellensatz (CNSS), application to list coloring, the graph polynomial.||Exercise Set 8||Combinatorial Nullstellensatz by Alon, in particular section 7|
|18.11.2008||Proof of the CNSS, CNSS2 and relation to the classical Hilbert Nullstellensatz||Exercise Set 9|
|25.11.2008||Several applications of the CNSS: Chevally-Warning Theorem, AFK Theorem (about p-regular subgraphs), Alon-Furedi Theorem (about covering the cube with hyperplanes)||Exercise Set 10|
|2.12.2008||Diameters of point sets and Borsuk's problem||Exercise Set 11|
|9.12.2008||Shannon capacity of graphs and Lovasz's theta-function||Exercise Set 12||C.E.Shannon: The zero capacity of a noisy channel|