Graph Theory

Time:15:20 - 17:20, Thu, 9/23/2022 - 12/30/2022

Venue:Zoom: 482 240 1589 PW: BIMSA

Speaker:Benjamin Sudakov (Professor)

Record: Yes

Level: Graduate

Language: English



The goal of this course is to give students an overview over the most fundamental concepts and results in modern graph theory.

The topics which we plan to cover include:

Basic notions: graphs, graph isomorphism, adjacency matrix, paths, cycles, connectivity

Trees, spanning trees, Cayley's formula,

Vertex and edge connectivity, 2-connectivity, Mader's theorem, Menger's theorem

Eulerian graphs, Hamilton cycle, Dirac's theorem

Matchings, Hall's theorem, Kőnig's theorem, Tutte's condition

Planar graphs, Euler's formula, basic non-planar graphs, platonic solids

Graph colourings, greedy colourings, Brooks' theorem, 5-colourings of planar graphs, Gallai-Roy theorem

Large girth and large chromatic number, edge colourings, Vizing's theorem, list colourings

Matrix-tree theorem, Cauchy-Binet formula

Hamiltonicity: Chvátal-Erdős theorem, Pósa's lemma, tournaments

Ramsey theory

Turán's theorem, Kővári-Sós-Turán theorem



Lecturer Intro

Benny Sudakov received his PhD from Tel Aviv University in 1999. He had appointments in Princeton University, the Institute for Advanced Studies and in University of California at Los Angeles. Sudakov is currently professor of mathematics in ETH, Zurich. He is the recipient of a Sloan Fellowship, NSF CAREER Award, Humboldt Research Award, is Fellow of the American Math. Society and was invited speaker at the 2010 International Congress of Mathematicians. He authored more than 300 scientific publications and is on the editorial board of 14  research journals.  His main scientific interests are combinatorics and its applications to other areas of mathematics and computer science.

Lecturer Email:

TA: Dr. Ruijie Xu,

DATESeptember 6, 2022
Related News
    • 0

      String Theory I

      Record: YesLevel: GraduateLanguage: EnglishPrerequisiteBasic mathematics (calculus, algebra, etc.); a textbook knowledge of General Relativity and Quantum Field Theory (including the very basics facts about supersymmetry); the elementary notions of differential geometry (Riemannian geometry, bundles, connections, etc.), Lie groups, and algebraic topology (homology & cohomology groups,etc.).Abst...

    • 1

      Knot Theory

      Note: Lecture on May 22 is cancelled.Course schedule:Lecture 1. Reidemeister moves, colouring invariants, linking numberLecture 2. The Kauffman bracket and the Jones polynomialLecture 3. Fundamental group. The knot groupLecture 4. The knot quandle. The complete knot invariantLecture 5. The braid group and the braid recognition algoritmLecture 6. Alexander's theorem and Markov's theoremLecture 7...