Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
 |
 |  |
 |
|
 |
|
 |
|
 |
||||||||
| 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 |
| Grade | There will be an oral exam at the end of the course. |
| 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 |
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.
