Topic outline

  • General

    Welcome! This is the home of the course MS-E1050, Graph Theory. The course starts on Monday 4.9., 10:15, with an online pre-lecture. The schedule of the course is as follows:

    Pre-lecture: Mon 4.9., 10-12, https://aalto.zoom.us/j/4620420079
    Lectures / exercise sessions (integrated):     Mon 10-12 (Y307), Thu 16-18 (M1), and Fri 10-12 (U5); 7.9.-22.9..
    Topical lectures (mandatory for the students whose project is in the topic in question. everybody welcome.): Mon 25.9., Thu 28.9., Fri 29.9., Mon 2.10. (same times and rooms as above)
    Project presentations:     Mon 9.10., Thu 12.10., Fri 13.10., same times and rooms as above. Also, one time during the week 16.-20.10. (to be decided)
    All events start 15 past the hour.


    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/


    Group projects: An integral part of this course will be self study projects, to be completed in small groups of 2-4 students. A list of suggested projects is given in the folder Projects in the left hand menu. The projects are reported orally during the period 9.-20.10.. You should also hand in a set of slides or a poster for each group. This can be the same material as you use as visual support for your oral presentation. Completed group works are graded as "accepted" or "excellent".

    Homework problems: There will be four sets of homework problems, with deadlines on 15.9., 22.9., 29.9., 20.10.. The final homework set will be twice as large as the three first ones. The homework is reported in writing via MyCourses. The three first homeworks are peer-graded, meaning that after the deadline, you will be given the hand-ins of two randomly selected fellow students to read and score. Your grades should be submitted within a week. The final homework sheet (or "final take-home exam") is graded by the teachers of the course.

    Grades: To pass the course with final grade n \in {1,2,3,4,5}, you need to have 
    • participated in an accepted group project.
    • been present for at least two of the three project report sessions, including your own presentation (or completed a complementary task).
    • obtained at least (28+12*n)% of the total score from the homeworks. 
    In addition, to get grade 5, your group project must be evaluated as "excellent".

    Teachers:
    Ragnar Freij-Hollanti, Lectures.
    Patricija Sapokaité, Exercises.


    Lecture schedule (with references to chapters in Diestel's book, and slides):
    Mon 4.9.: Introductions, basics, exploratory exercises.
    Thu 7.9.: Subgraphs and graph homomorphisms
    Fri 8.9.: Minors
    Mon 11.9.: Matchings
    Thu 14.9.: Connectivity
    Fri 15.9.: Planar graphs
    Mon 18.9.: Kuratowski's Theorem
    Thu 21.9.: Colourings
    Fri 22.9.: Perfect graphs

    Topical lectures (with references to chapters in Diestel's book, and slides):
    Mon 25.9.: A friendly introduction to extremal graph theory
    Thu 28.9.: A friendly introduction to algebraic graph theory
    Fri 29.9.: A friendly introduction to random graphs
    Mon 2.10.: A friendly introduction to Ramsey theory or perfect graphs

    Project presentations (with slides/posters):
    Mon 9.10.: Project presentations in extremal graph theory
    Thu 12.10.: Project presentations in algebraic graph theory
    Fri 13.10.: Project presentations on random graphs and miscalleneous