清华主页 EN
导航菜单

Graph Theory

来源: 09-22

时间: 15:20 - 17:20, Thu, 9/22/2022 - 12/29/2022

地点:Zoom: 482 240 1589 PW: BIMSA

主讲人: Benjamin Sudakov (Professor)

Record: Yes

Level: Graduate

Language: English


Abstract

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


Syllabus

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: benny.sudakov@gmail.com

TA: Dr. Ruijie Xu, xuruijie@bimsa.cn


返回顶部
相关文章
  • Graph Theory

    Record: YesLevel: GraduateLanguage: EnglishPrerequisiteAbstractThe 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, connectivityTrees, spanning trees, Cayley's formula,Vertex and edge connectivity, 2-connec...

  • Graph algorithm

    Record: NoLevel: GraduateLanguage: ChinesePrerequisiteDiscrete math.AbstractIn this course, we introduce basic concepts in graph theory and complexity theory, then study graph algorithms with a focus on matching and network flows.Reference1. Introduction to Graph Theory, by Douglas B. West.2. Modern Graph Theory, by Bela Bollobas.3. The Design and Analysis of Algorithms, by Dexter Kozen.Syllabu...