Topic outline

  • General

    Welcome! This is the home of the course MS-E1050, Graph Theory. The course starts on Monday 5.9., 10:15, with an online pre-lecture. I expect everybody to take part in this pre-lecture, which is given at the Zoom address https://aalto.zoom.us/j/4620420079. (In particular, there will be no exercise session on campus on 5.9.) After this, the course proceeds with lectures on Thursdays and Fridays 8.9.-14.10., and exercises on Mondays 12.9.-10.10. There will also be a final session during the week 17.10.-21.10. (time to be decided), to conclude the course and discuss the last homework set.

    What is graph theory? Graphs are widely used as modelling devices in a broad array of applied sciences, including scheduling, networking, and material physics. Remarkably, graphs are also used to model other purely mathematical objects such as knots, groups and manifolds. In this course, our focus will be on the combinatorial theory of graphs, with views towards its rich interplay with algebra, computer science and probability theory.

    The course is aimed at master's and doctoral students, so mathematical maturity comparable to a bachelor in computer science, mathematics or operations research is expected.

    Literature: We will use Reinhard Diestel's book Graph Theory, see http://diestel-graph-theory.com/

    Homework: The course will be graded based on five peer-graded homework sets, each containing five "exercises" and two "problems". The four best homework performances will count towards your final grade. We reserve the right to require an oral exam in addition, if we are not sure about the grade based on the homework. The homework is reported in writing via MyCourses, with a deadline on Mondays 10am. After the deadline, you will be given the hand-ins of two randomly selected fellow students to read and score. These should be graded within a week.

    Teachers:
    Ragnar Freij-Hollanti, Lectures.
    Patricija Sapokaité, Exercises (Y307)
    Nataliia Kuschnerchuk, Exercises (https://aalto.zoom.us/j/4620420079)

    Lectures: Thu 16-18 (M1) and Fri 10-12 (Y405).
    Excercises: Mon 10-12 (Y307 and on Zoom: https://aalto.zoom.us/j/4620420079)

    All events start 15 past the hour.

    Lecture schedule (with references to chapters in Diestel's book, and slides):
    Lecture 0 (Monday 5.9.): Introductions, basics, exploratory exercises. (slides 1-21)
    Lecture 1: Basics (most of Chapter 1, slides 22-38)
    Lecture 2: Basics (most of Chapter 1, slides 39-57)
    Lecture 3: Matchings (2.1-2, slides 58-71)
    Lecture 4: Connectivity (3.1,3, slides 72-79, 84-100)
    Lecture 5: Plane and Planar graphs (3.3, 4.2, 101-107, 114-121)
    Lecture 6: 3-connectivity and Kuratowski's Theorem (3.2, 4.3-6, 108-112, 122-134)
    Lecture 7: Colourings (5.1-4, 135-150)
    Lecture 8: Perfect graphs (5.5, 151-160)
    Lecture 9: Perfect graphs (5.5, 161-166)
    Lecture 10: Random graphs (11.1-3, 167-174)
    Lecture 11: Extremal graph theory (7.1-3)
    Lecture 12: Ramsey theory (9.1-2)