Combinatorics
 BMS basic Course -- Diskrete Strukturen I
Summer Term 2009

Sommersemester 2009
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 0230 L 149
Mo 8-10, MA 550
Mo 12-14, MA 551


 Zeichnung

News:

This is a Berlin Mathematical School (BMS) Basic Course, and will thus be taught in English.

This is a Basic Graduate Course on Combinatorics/Discrete Mathematics.

This is also the first course of the “Diskrete Strukturen” course series. It will be continued by Graph Theory course (Discrete Structures II), Winter term 09/10.

Contents:

Combinatorics is a branch of pure mathematics concerning the study of mostly finite objects. It is related to many other areas of mathematics, such as algebra, probability theory and geometry, as well as to applied subjects in computer science and statistical physics. Aspects of combinatorics include "counting" the objects satisfying certain criteria (enumerative combinatorics), deciding when the criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and finding algebraic structures these objects may have (algebraic combinatorics).

Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. The goal of this course will be to provide you with a broad overview – and with a firm, concrete “working knowledge” on basic combinatorial principles, tools, methods, theories, and results.

Some Chapters:
  1. Introduction
  2. Basic Counting
  3. Generating Functions
  4. Combinatorics of Finite Sets
  5. Posets
  6. Duality Theorems
  7. Polya Theory
  8. Design Theory
  9. Graphs and Chromatic Number
  10. Gray Codes and De Brujin Sequences
  11. Catalan Families

Tutorial:

Wednesday 14-16, E-N 189
Daniel Heldt

Wednesday, 12-14, MA 644
Dr. Hans Raj Tiwary


The tutorials start on Wednesday, 2009/04/29!

Problem sets

  1. Practise sheet [ps] [pdf]
  2. Practise sheet [ps] [pdf]
  3. Practise sheet [ps] [pdf] (this file was updated on 06.05; exercise 3c is modified)
  4. Practise sheet [ps] [pdf]
  5. Practise sheet [ps] [pdf] Solutions have to be handed in!
  6. Practise sheet [ps] [pdf]
  7. Practise sheet [ps] [pdf]
  8. Practise sheet [ps] [pdf] (please check the dates for oral exams and register if you want to do an oral exam!)
  9. Practise sheet [ps] [pdf]
  10. Practise sheet [ps] [pdf] Solutions have to be handed in!

Terms to recieve a certificate / credit-points:

At the beginning of every tutorial every participant has to mark in a list, which exercises of the actual sheet she/he solved and is able to present. If somebody marks an exercise she/he is not able to present in a satisfying way, ALL exercises of this sheet will be disregarded and therefore not counted (also, each exercise is only counted once, even if presented in both tutorials).

Also there will be two or three sheets marked as mandatory. These will be handed in and corrected by the tutors. To recieve a certificate for the tutorials (Schein), you have to mark at least 50% of the exercises and reach 50% of the points on the mandatory sheets.

To gain credit points / get a certificate for the module DS I you have to take an oral exam, after acquiring the certificate for the tutorials.

Oral exams are scheduled for Wednesday 15th July 2009 in the afternoon and Tuesday 6th October 2009. If you want to participate, please send an email to Daniel Heldt. If you are unable to attend at one of the days, please also send a message.

References:

Last modified July 2009