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

Sommersemester 2011
Prof. Stefan Felsner
Sprechstunde n.V.

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


 Zeichnung

News:

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

This is also the first course of the “Diskrete Strukturen” course series. It will be continued by Graphentheorie (Diskrete Strukturen II), Winter term 11/12.

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. Typical combinatorial questions are: Does a set with certain properties exist at all? If yes, how many are there? How do I find them? Combinatorics abounds with beautiful problems that are easily understood, but very often a real challenge to solve.

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.

The course will cover most of the following topics:
  1. Basic Counting
  2. Generating Functions
  3. Combinatorics of Finite Sets
  4. Posets
  5. Duality Theorems
  6. Polya Theory
  7. Design Theory
  8. Graphs and Chromatic Number
  9. Gray Codes and De Brujin Sequences
  10. Catalan Families

Tutorials:

 The tutorials start on Tuesday, 2011/04/19!

Problem sets

  1. Practise sheet [ps] [pdf]
  2. Practise sheet [ps] [pdf]
  3. Practise sheet [ps] [pdf] (update: please hand in exercise #5 in written form; update 2: fixed first exercise)
  4. Practise sheet [ps] [pdf]
  5. Practise sheet [ps] [pdf]
  6. Practise sheet [ps] [pdf], Pictures of the posets of exercise 5 (pdf)
  7. Practise sheet [ps] [pdf] (fixed exercise 4)
  8. Practise sheet [ps] [pdf]
  9. Practise sheet [ps] [pdf]
  10. Practise sheet [ps] [pdf]
  11. Practise sheet [ps] [pdf]
  12. Practise sheet [ps] [pdf]

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). We expect a better presentation and solutions of master- and BMS students, compared to the ones, acceptable from bachelor students. Besides the exercises to present, there is every week one exercise which has to be handed in in written form. This exercise will be corrected as usual. To recieve a certificate for the tutorials (Schein), you have to solve at least 50% of the exercises including the written exercises.
To complete the modul participants have to pass an additional oral exam. Exams will take place on July 12th (passed) and July 19th (full!), 2011. Please contact Daniel Heldt to make an appointment and give him the yellow formular from the "Prüfungsamt".
Additional dates for oral exams: August, 18th, September, 19th and November 3rd, 2011.

The certificates for the participation in the tutorials can now be fetched at Frau Klink's office (MA 501).

References:

Last modified 23. August 2011