---

Time & Place

The course starts in the second week on Tuesday 23.9.2008, there is no course and no exercise session in the first week of the semester.
Lecture: Tuesdays 10:15-12:00, CAB G 59. The lecturers are:
Exercises: Thursdays 16:15-17:00, CAB G 19.2. The teaching assistant is:

Contents

• Course Description
• Grades, Exercises, Exam
• References and Additional Reading
• Course Summary and Exercises by Week

Course Description

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.

Procedures, exercises, exam

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.

References and Additional Reading

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.
http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf

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.
http://www.math.tau.ac.il/~nogaa/PDFS/tools1.pdf

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.
http://cuscus.math.uwaterloo.ca/pstuff/tools.pdf

Combinatorics and commutative algebra, by Stanley, Richard P. Second edition. Progress in Mathematics, 41. Birkhaeuser Boston, Inc., Boston, MA, 1996.

Course Summary and Exercises by Week

There is no course and no exercise session in the first week of the semester.

Date	Content	Exercises	References
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

---