Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Théorie des graphes avancée (24h, 3 ECTS)

Responsable: Reza Naserasr

Schedule of course for 2023 – 2024

Reza Naserasr(12h, Sept 18, Sept 25, Oct 02, Oct 09) Lecture Notes Here

Matej Stehlik (12h, Oct 16, Oct 23, Oct 30, Nov 06)

Exam: 27th November 2024, 12:45-15:45 in room SG 1004

Presentations: also to be decided.

All lectures will be given in English, but questions can be addressed in French.

General objectives

Graphs are fundamental tools for most areas of computer science.

Therefore there are two complimentary goal in this course:

The first goal is for all students attending to the course to learn tools and techniques on dealing with problems on graph theory. This would help in particular with stating your research problem using language of graph theory when needed.

The second goal of the course is to offer a deeper look for those student who are persuaded to continue graph theory as a main research career.

The number of particular subjects to be covered is too large, thus there will be flexibility on choosing the subject. That would depend on the common interest of students and teachers. A general list of subjects is given below, but the list itself could also be extended at request. If you are curios to learn a certain subject, then do not hesitate to write to the teachers of the course.

- Minor theory, planarity, etc.

- Various notions of coloring, such as proper vertex coloring, fractional coloring, edge-coloring, ...

- Important graph parameters: clique number, independence number, coloring number, Lovasz theta-function,...

- Graph homomorphisms and graph products,

- Algorithms, in particular: greedy algorithms, min-max theorems, linear programming ...

- Structured graphs: interval graph, permutation graphs, comparability graphs, perfect graphs, ...

- Eigenvalue techniques,

- Ramsey theory,

- Probabilistic methods and random graphs,

- Packing problems,

- Topological methods in graph theory,

- Graph limits

Plans of the course for 2024-2025 (subject to modification by request)

I - By Reza Naserasr - 4 lectures (Sept 18, Sept 25, Oct 02, Oct 09 Wednesday 12:45)

Lectures will cover some but not all of the following subjects.

1. Ramsey theory,

2. Vizing's theorem, maximum matchings and vertex cover, Menger theorem and its application to maximum matching in bipartite graphs, Tutte theorem, Marriage Hall theorem. Proving that 3-edge-coloring problem is NP-complete,

2. Connection of the notions of planarity, vertex coloring, edge-coloring, hamiltonicity and nowhere-zero flows: we show how the four-color theorem has given birth to all these theories.

4. Homomorphisms of graphs. Extension of theories to signed graphs

II - By Matej Stehlik - 4 lectures (Oct 16, Oct 23, Oct 30, Nov 06 Wednesday 12:45)

1. Chromatic number of graphs. Upper and lower bounds, different ways of showing that the gap between the chromatic number and the clique number can be arbitrarily large.

2. Introduction to extremal graph theory. Maximum number of edges in triangle-free graphs, and more generally in graphs containing no cliques of a given size.

3. Chinese postman problem, T-joins and T-cuts.

4. Travelling salesman problem. Inapproximability of the general TSP, approximation algorithms for metric TSP.

Pré-requis

1. A basic knowledge on graph theory such as stable set, clique number, chromatic number...

2. Classic graph algorithms such as shortest path or Ford-Fulkerson algorithm

3. Good knowledge on algorithmic complexity theory

4. Dynamic programming

Bibliographie

Graph Theory, by R. Diestel

Graph Theory with applications, A. Bondy, U.S.R. Murty, Springer-verlag, 2008.

Introduction the graph theory, by D. West.

Équipe pédagogique

Reza Naserasr (CNRS, IRIF Université de Paris), Matej Stehlik (Prof. IRIF Université de Paris)

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA