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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Extremal Combinatorics: Explicit Constructions SS 05
Theory of Combinatorial Algorithms Institute of Theoretical Computer Science Department of Computer Science ETH Zurich

Extremal Combinatorics: Explicit Constructions (251-0458-00) SS 05



Time & Place


Instructors

Lecturer: Tibor Szabó
IFW B48.1/ Tel: (01) 632-0858. e-mail: szabo@inf.ethz.ch

Assistant: Milos Stojakovic
IFW B43/ Tel: (01) 632-7239. e-mail: smilos@inf.ethz.ch

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 succesful in providing existence proofs of certain extremal objects without providing effiecient 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. One particluar 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. In the course we will develop the necessary algebraic background needed to understand our current knowledge.
Other topics include selected problems from Ramsey Theory. Here probabilistic arguments usually do much better, hence our goal will be the understanding of relatively good 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 mathemtics 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.

Grading

There will be an oral exam at the end of course.

Language

English

Exercises and solutions

Exercise set 1: Exercises 1, 2, 4 from Chapter 1. Solutions: PS.
Exercise set 2: Exercises 6, 7, 10 from Chapter 1. Solutions: PS.
Exercise set 3: Exercises 12, 13, 28 from Chapter 1. Solutions: PS.
Exercise set 4: Exercises 7, 10, 12 from Chapter 2. Solutions: PS.
Exercise set 5: Exercises 1, 2, 7, 14 from Chapter 3. Solutions: PS.
Exercise set 6: Exercises 1, 2 from the 8th Lecture. Solutions: PS.

Literature

Other (graph theory) texts:

Links