Combinatorial Structures and Algorithms

Prof. Dr. Angelika Steger

Advanced Topics in Discrete Mathematics (SS 05)

	Instructors: Dr. Stefanie Gerke Prof. Dr. Angelika Steger Dr. Tibor Szabo
	Time and Place: Monday, 12.30 - 14.00, IFW B 42
	Topics: Szemerédi's regularity lemma is one of the most important tools of modern combinatorics with applications in extremal graph theory, in the theory of approximation algorithms, property testing and more. Roughly speaking, the lemma says that every large graph contains a large subgraph that is very regular and thus has lots of nice properties that can be used to prove results for very large graphs. In this seminar we want to develop a solid understanding of the lemma and of some of its applications.
	Participants: Students of mathematics and computer science with basic knowledge of graph theory and theory of algorithms.
	Grading: In order to receive a grade or testat students must present a lecture (in English). The topics can be chosen at the first meeting.
	Literature: Will be distributed at the first meeting.
	Schedule: 11.4. Introduction to Szemeredi's regularity lemma. 18.4. Erdös-Stone-Simonovits Theorem 2.5. Arithmetic progressions 9.5. Topological Cliques 30.5. Blow-up lemma 6.6. Testing regularity is Co-NP but there is an polynomial time algorithm finding a regular partition 13.6. Approximating Max-Cut 20.6 Quick approxmitation to matrices