Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Extremal Combinatorics - SS 07
Theory of Combinatorial Algorithms Institute of Theoretical Computer Science Department of Computer Science ETH Zurich

Extremal Combinatorics (251-0458-00) - SS 07

General Information

Lectures Friday, 10-12 @ CAB G52.
Lecturer: Tibor Szabó CAB G31.2/ Tel: 044 632-0858. e-mail: szabo@inf.ethz.ch
Exercises Friday, 13-14 @ CAB G52.
Assistant: Philipp Zumstein CAB G17/ Tel: 044 632-7318. e-mail: zuphilip@inf.ethz.ch
Language    English
GradeThere will be an oral exam at the end of the course.

Lecture Notes

Exercises and Solutions

There will be weekly exercise sets.
date exercise sheet sample solution
Exercise Set 1 23.03.07 ex1.pdf
recitation1.pdf
sol1.pdf
Exercise Set 2 30.03.07 ex2.pdf
recitation2.pdf
sol2.pdf
Exercise Set 3 20.04.07 ex3.pdf sol3.pdf
Exercise Set 4 27.04.07 ex4.pdf sol4.pdf Exercise 2 is still incomplete. Any suggestions?
Exercise Set 5 04.05.07 ex5.pdf sol5.pdf
Exercise Set 6 11.05.07 ex6.pdf sol6.pdf
Exercise Set 7 25.05.07 ex7.pdf sol7.pdf
Exercise Set 8 01.06.07 ex8.pdf sol8.pdf New second exercise
Exercise Set 9 08.06.07 ex9.pdf sol9.pdf
Exercise Set 10 15.06.07 ex10.pdf sol10.pdf independence number is at most k

Abstract of the course

Vaguely speaking, extremal combinatorics is concerned with the determination of the extremum of (combinatorial) functions over some domain of (combinatorial) objects. One classical example is the problem of Mantel: "How many edges can a triangle-free graph contain on n vertices?" For this question, the answer is precisely known; partly because the extremal example (the triangle-free graph with the most number of edges) is well-understood and unique. The situation is less satisfactory in other basic problems of similar type.

The probabilistic method is quite successful in providing existence proofs of certain extremal objects without providing efficient ways to construct them. This is good enough in some cases, but often in theoretical computer science an explicit object, maybe even with slightly suboptimal parameters, is more desirable. Another reason to study explicit constructions is that there are a number of problems where existing probabilistic methods are simply inferior to other, mostly ad hoc algebraic techniques.

In the course we plan to focus mainly on explicit constructions, but also touch upon some of the related probabilistic ones. Explicit constructions are often based on simple algebraic structures. In the course we will develop the necessary algebraic background needed to understand them. One particular topic we intend to cover more in depth is the problem of Zarankiewicz, i.e. "How many edges can a graph on n vertices have if it does not contain a fixed complete bipartite subgraph". This is one of the major open problems of Extremal Graph Theory; an asymptotic solution is known only for certain values of the parameters.

Other topics include selected problems from Ramsey Theory. Here probabilistic arguments usually do much better, hence our goal will be the understanding of the best known explicit constructions. We plan to include the very recent advance on the bipartite Ramsey question based on combinatorial number theory, in particular the Bourgain-Katz-Tao Theorem.

The course is intended for theoretical computer science and mathematics students who are interested in combinatorics. Students of algebra might also be interested in order to see some of their theory, like the Nullstellensatz applied.


Literature

Some parts of the material is covered in the following books: Other (graph theory) texts:

Last modified:  2007 Juni 22, by Philipp Zumstein