MATH-360 / 5 crédits

Enseignant: Janzer Oliver

Langue: Anglais


Summary

The course aims to introduce the basic concepts and results of modern Graph Theory.

Content

In this course we will cover the following topics:

  • trees
  • connectivity
  • Eulerian and Hamiltonian cycles
  • matchings
  • planar graphs
  • graph colouring
  • Ramsey theory
  • extremal problems

 

Keywords

Graph, isomorphism, complement, complete, bipartite, connected, path, circuit, cycle, planar, tree, spanning, Eulerian, Hamiltonian, colouring, Ramsey theory, forbidden subgraph, extremal graph.

Learning Outcomes

By the end of the course, the student must be able to:

  • Illustrate simple examples of graphs satisfying certain properties
  • State definitions and results of graph theory
  • Verify hypotheses of theorems for applications
  • Prove theorems and other properties
  • Justify the main arguments rigorously
  • Apply relevant results to solve problems
  • Modify the main proofs if needed, to solve similar problems

Teaching methods

In-person lectures + in-person exercise classes covering weekly exercise sheets.

Expected student activities

The students are expected to attend the lectures and the exercise classes. In addition, they are expected to attempt the problems on the exercise sheets and to submit their solutions of a selected subset of the exercises for grading.

Assessment methods

Written final exam

Supervision

Office hours No
Assistants Yes
Forum Yes

Resources

Bibliography

  • Diestel : Graph Theory (Springer)
  • Bollobas : Modern Graph Theory (Springer)
  • West: Introduction to Graph Theory

Ressources en bibliothèque

Notes/Handbook

Lecture notes will be provided.

Moodle Link

Prerequisite for

MATH-467: Probabilistic methods in combinatorics

MATH-526: Algebraic methods in combinatorics

Dans les plans d'études

  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Graph theory
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel

Semaine de référence

Jeudi, 13h - 15h: Cours GCA330

Jeudi, 15h - 17h: Exercice, TP GCA330

Cours connexes

Résultats de graphsearch.epfl.ch.