Universität Wien

902416 VO Selected Topics in Graph Theory (2005S)

Selected Topics in Graph Theory

0.00 ECTS (2.00 SWS), SPL 25 - Mathematik

Vorbesprechung am 3. März 2005

Details

Language: German

Examination dates

Lecturers

Classes (iCal) - next class is marked with N

  • Wednesday 02.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 03.03. 13:00 - 14:00 Seminarraum
  • Wednesday 09.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 10.03. 13:00 - 14:00 Seminarraum
  • Wednesday 16.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 17.03. 13:00 - 14:00 Seminarraum
  • Wednesday 06.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 07.04. 13:00 - 14:00 Seminarraum
  • Wednesday 13.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 14.04. 13:00 - 14:00 Seminarraum
  • Wednesday 20.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 21.04. 13:00 - 14:00 Seminarraum
  • Wednesday 27.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 28.04. 13:00 - 14:00 Seminarraum
  • Wednesday 04.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Wednesday 11.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 12.05. 13:00 - 14:00 Seminarraum
  • Wednesday 18.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 19.05. 13:00 - 14:00 Seminarraum
  • Wednesday 25.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Wednesday 01.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 02.06. 13:00 - 14:00 Seminarraum
  • Wednesday 08.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 09.06. 13:00 - 14:00 Seminarraum
  • Wednesday 15.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 16.06. 13:00 - 14:00 Seminarraum
  • Wednesday 22.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 23.06. 13:00 - 14:00 Seminarraum
  • Wednesday 29.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Thursday 30.06. 13:00 - 14:00 Seminarraum

Information

Aims, contents and method of the course

I decided to choose matching theory as the topic of this course since it is an example of a well-developed theory in the relatively young branch of mathematics called graph theory.
The intereset in matchtings arose from the following observation of Tait (1880): "The
four-colour theorem is equivalent to the statement that every planar cubic graph without
cut edges is 3-edge-colourable." Using this observation, Tait wanted to prove the four-colour theorem. Although he failed with this project, his efforts led to a beautiful theory.

I will start the course with the fundaments of matching theory, i.e. Hall's Theorem, Tutte's Theorem and Edmonds' Algorithm for finding a matching of maximal size.
Then we will turn to the perfect matching polytope, which is defined as the set of convex
combinations of perfect matchings in a vector space naturally associated to every graph. Finally we will consider the matching lattice, being the set of integer linear combinations of perfect matchings.

Assessment and permitted materials

Minimum requirements and assessment criteria

Examination topics

Reading list

(1) L. Lovasz und M. D. Plummer, Matching Theory, North Holland, 1986.
(2) L. Lovasz, Matching structure and the matching lattice, J. Combin. Theory Ser. B, 43 (1987), 187 - 222.
(3) R. Diestel, Graphentheorie, 2. Auflage, Springer-Verlag, 2000.
http://www.math.uni-hamburg.de/home/diestel/books/graphentheorie/index.html
(4) J. A. Bondy und U. S. R. Murty, Graph Theory with Applications, North Holland, New York, 1976 http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html

Association in the course directory

Last modified: Mo 07.09.2020 15:51