Topic outline

  • General

    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.

    The course will be graded based on three homework sets, each containing 7 "exercises" and 3 "problems". We reserve the right to require an oral exam in addition, if we are not sure about the grade based on the homework.

    Welcome!

    Teachers:
    Ragnar Freij-Hollanti, Lectures.
    Matteo Allaix, Exercises (live)
    Perttu Saarela, Exercises (online)

    Lectures: Mon 10-12 and Thu 16-18.
    Excercises: Fri 10-12.

    All events start 15 past the hour. The lectures and online exercises are given at the address https://aalto.zoom.us/j/67316483735. The Zoom room is protected by a password, this is the last name of the author of the course book (see the folder "Materials"). Make sure to connect and test your technology in advance of the start of the lecture. The live exercises are given in room R1 at Rakentajanaukio 4.

    The course has a discussion forum on Zulip: https://mse1050graphtheory2021.zulipchat.com. Contact Matteo if you have problems accessing the forum.


    Lecture schedule (with references to chapters in Diestel's book):
    1) Basics (1.1-4, slides 1-26)
    2) Basics (1.5-7,9, slides 27-50)
    3) 3-connected graphs and Menger's Theorem (3.2-3)
    4) Matchings (2.1,2)
    5) Plane and planar graphs (4.2-6)
    6) Colorings (5.1-4)
    7) Perfect graphs (5.5)
    8) Extremal graph theory (7.1-3)
    9) Szemeredi’s Regularity Lemma (7.4-5)
    10) Ramsey theory (9.1-2)
    11) Chromatic polynomial and flow polynomial
    12) The Tutte polynomial