Combinatorial Structures and Algorithms

Prof. Dr. Angelika Steger

Advanced Topics in Discrete Mathematics (SS 07)

	Instructors: Prof. Dr. Angelika Steger Dr. Tibor Szabo
	Time and Place: Monday, 14-16, CAB G 59 First meeting and assignment of talks: Monday, March 19.
	Topics: Numerous important and fascinating topics in discrete mathematics can only be scratched in regular courses. The aim of this seminar is to study papers which bring the students to the forefront of today's research topics. Each semester we focus on a particular topic. Previous years: SS05: Szemeredi's regularity lemma SS06: Property testing This year we study various aspects of extremal graph theory.
	Participants: The seminar is open for both students from mathematics and students from computer science. As prerequisite we require that you passed at least one of the following three courses: Algorithms, Probability, and Computing, Graph Theory, Randomized Algorithms and Probabilistic Methods. A note for Bachelor students: We do allow (and welcome) interested and motivated Bachelor students. However, please keep in mind that this is a seminar which is called Advanced Topics. This means that you will certainly find seminars which are easier and require less work. On the other hand, if you are looking for a seminar which provides some challenge and brings you in touch with current research -- this might be what you are looking for.
	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: [1] Sudakov, Making a K4-free graph bipartite, Combinatorica, to appear. [2] Keevash, Sudakov, Sparse halves in triangle-free graphs, Journal of Combinatorial Theory, Series B 96 (2006) 614-620. [3] Füredi, Naor, Verstraete, On the Turan Number for the Hexagon, Advances in Mathematics 203(2), 476-496 (2006). [4] de Caen, The current status of Turán's problem on hypergraphs, Extremal Problems for Finite Sets, Bolyai Society Mathematical Studies 3 (eds. Frankl, Füredi, Katona and Miklós) 1994; pp. 187-197. [5] de Caen, Furedi, The maximum size of 3-uniform hypergraphs not containing a Fano plane, Journal of Comb. Theory B, 78 (2000), 274-276. [6] Keevash, Sudakov, The Turan number of the Fano plane, Combinatorica 25 (5) (2005) 561–574. [7] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars combinatoria, 16 (1983), 5-10. [7] Kostochka, A. V., A class of constructions for Turán's (3,4)-problem, Combinatorica 2 (1982), no. 2, 187--192. [9] Z. Furedi, A. Kundgen, Turan problems for weighted graphs, J. of Graph Theory 40 (2002), 195-225.
	Schedule: *April 23:* Salvatore Bonaccorso: Making a K4-free graph bipartite Benjamin Abt: Sparse halves in triangle-free graphs *Mai 7:* Jörg Priewasser and Henning Thomas: On the Turan Number for the Hexagon *May 14:* Stefan Ravizza: Turán's problem on hypergraphs Thomas Rast: The Turan number of the Fano plane