## Benjamin Sudakov: Catalogue data in Spring Semester 2019 |

Name | Prof. Dr. Benjamin Sudakov |

Field | Mathematics |

Address | Institut für Operations Research ETH Zürich, HG G 65.1 Rämistrasse 101 8092 Zürich SWITZERLAND |

Telephone | +41 44 632 40 28 |

benjamin.sudakov@math.ethz.ch | |

URL | http://www.math.ethz.ch/~sudakovb |

Department | Mathematics |

Relationship | Full Professor |

Number | Title | ECTS | Hours | Lecturers | |
---|---|---|---|---|---|

252-4202-00L | Seminar in Theoretical Computer Science The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 credits | 2S | A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov | |

Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | ||||

Objective | To get an overview of current research in the areas covered by the involved research groups. To present results from the literature. | ||||

Prerequisites / Notice | This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal minimal requirement is passing of one of the courses Algorithms, Probability, and Computing, Randomized Algorithms and Probabilistic Methods, Geometry: Combinatorics and Algorithms, Advanced Algorithms. (If you cannot fulfill this restriction, because this is your first term at ETH, but you believe that you satisfy equivalent criteria, please send an email with a detailed description of your reasoning to the organizers of the seminar.) | ||||

401-3052-05L | Graph Theory | 5 credits | 2V + 1U | B. Sudakov | |

Abstract | Basic notions, trees, spanning trees, Caley's formula, vertex and edge connectivity, blocks, 2-connectivity, Mader's theorem, Menger's theorem, Eulerian graphs, Hamilton cycles, Dirac's theorem, matchings, theorems of Hall, König and Tutte, planar graphs, Euler's formula, basic non-planar graphs, graph colorings, greedy colorings, Brooks' theorem, 5-colorings of planar graphs | ||||

Objective | The students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems. | ||||

Lecture notes | Lecture will be only at the blackboard. | ||||

Literature | West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture. | ||||

Prerequisites / Notice | Students are expected to have a mathematical background and should be able to write rigorous proofs. NOTICE: This course unit was previously offered as 252-1408-00L Graphs and Algorithms. | ||||

401-3052-10L | Graph Theory | 10 credits | 4V + 1U | B. Sudakov | |

Abstract | Basics, trees, Caley's formula, matrix tree theorem, connectivity, theorems of Mader and Menger, Eulerian graphs, Hamilton cycles, theorems of Dirac, Ore, Erdös-Chvatal, matchings, theorems of Hall, König, Tutte, planar graphs, Euler's formula, Kuratowski's theorem, graph colorings, Brooks' theorem, 5-colorings of planar graphs, list colorings, Vizing's theorem, Ramsey theory, Turán's theorem | ||||

Objective | The students will get an overview over the most fundamental questions concerning graph theory. We expect them to understand the proof techniques and to use them autonomously on related problems. | ||||

Lecture notes | Lecture will be only at the blackboard. | ||||

Literature | West, D.: "Introduction to Graph Theory" Diestel, R.: "Graph Theory" Further literature links will be provided in the lecture. | ||||

Prerequisites / Notice | Students are expected to have a mathematical background and should be able to write rigorous proofs. |