Institut für Theoretische Informatik, Algorithmik

Seminar: Proofs from THE BOOK - Perlen der diskreten Mathematik

Sommersemester 2006

Allgemeines

Beschreibung

Dem 1996 verstorbenen ungarischen Mathematiker Paul Erdős zufolge, hält Gott ein Buch - nämlich das BUCH - mit den schönsten und elegantesten mathematischen Beweisen unter Verschluss. Erdős' höchstes Ziel war es, eben solche Beweise aus dem BUCH zu finden.

Martin Aigner und Günter Ziegler veröffentlichten nach Erdős' Tod 1998 das Buch „Proofs from THE BOOK“ [1], das inzwischen auch in deutscher Sprache unter dem Titel „Das BUCH der Beweise“ [2] erschienen ist. In ihrer Sammlung, die zum Teil gemeinsam mit Paul Erdős entstanden ist, findet man 35 Beweise, die wegen ihrer Eleganz als vielversprechende Kandidaten für BUCH-Beweise gelten.

In diesem Seminar werden die Teilnehmer eine Auswahl der folgenden Probleme aus dem Buch der Beweise erörtern. Die fettgedruckten Themen werden Gegenstand des Seminars sein. Sie sind ab der zweiten Auflage alle im Buch enthalten; in der ersten Auflage fehlt Kapitel 21.

Zahlentheorie

1. Sechs Beweise für die Unendlichkeit der Primzahlen

2. Das Bertrandsche Postulat

3. Binomialkoeffizienten sind (fast) nie Potenzen

4. Der Zwei-Quadrate-Satz von Fermat

5. Jeder endliche Schiefkörper ist ein Körper

6. Einige irrationale Zahlen

7. Drei Mal pi^2/6

Geometrie

8. Hilberts drittes Problem: Zerlegung von Polyedern

9. Geraden in der Ebene und Zerlegungen von Graphen

10. Wenige Steigungen

11. Drei Anwendungen der Eulerschen Polyederformel

12. Der Starrheitssatz von Cauchy

13. Simplexe, die einander berühren

14. Stumpfe Winkel

15. Die Borsuk-Vermutung

Analysis

16. Mengen, Funktionen, und die Kontinuumshypothese

17. Ein Lob der Ungleichungen

18. Ein Satz von Pólya über Polynome

19. Ein Lemma von Littlewood und Offord

20. Der Kotangens und der Herglotz-Trick

21. Das Nadel-Problem von Buffon

Kombinatorik

22. Schubfachprinzip und doppeltes Abzählen

23. Drei berühmte Sätze über endliche Mengen

24. Gut genug gemischt?

25. Gitterwege und Determinanten

26. Cayleys Formel für die Anzahl der Bäume

27. Vervollständigung von Lateinischen Quadraten

28. Das Dinitz-Problem

29. Identitäten und Bijektionen

Graphentheorie

30. Ein Fünf-Farben-Satz

31. Die Museumswächter

32. Der Satz von Turán

33. Kommunikation ohne Fehler

34. Von Freunden und Politikern

35. Die Probabilistische Methode

Ablauf

Die Teilnehmerzahl ist auf 18 beschränkt. Die endgültige Teilnehmerliste wird bei der Vorbesprechung am 25.04. festgelegt. Die Teilnahme an der Vorbesprechung ist für alle Seminarteilnehmer verpflichtend.

Eine Seminarsitzung besteht aus 3-5 Untervorträgen des jeweiligen Themas. Dabei soll ein Vortrag in der Regel 15-20 Minuten dauern (plus anschließende Diskussion). Jeder Seminarteilnehmer muss alle Vorträge vorbereiten. Über den tatsächlich Vortragenden entscheidet dann das Los. Es besteht die Möglichkeit, vorab einen Joker zu setzen, der den Seminarteilnehmer von allen Vorträgen der jeweiligen Sitzung befreit. Jeder Teilnehmer kann zweimal einen Joker setzen.

Um Fragen bezüglich der Themen zu beantworten, gibt der jeweilige Betreuer eine Woche im Voraus ein bis zwei Sprechstundentermine an.

Als Vortragshilfsmittel kann neben der Tafel auch der Tageslicht-Projektor verwendet werden. Folien und Folienschreiber sind im Sekretariat in Raum 321 erhältlich.

Es wird keine schriftliche Ausarbeitung verlangt.

Termine

25.04. Vorbesprechung
02.05. Sitzung 01: Sechs Beweise für die Unendlichkeit der Primzahlen Rob van Stee
09.05. Sitzung 02: Das Bertrandsche Postulat (inkl. Anhang) Martin Nöllenburg
16.05. Sitzung 03: Geraden in der Ebene und Zerlegung von Graphen Alexander Wolff
23.05. Sitzung 04: Drei Anwendungen der Eulerschen Polyederformel Alexander Wolff
30.05. Sitzung 05: Stumpfe Winkel Rob van Stee
06.06. Sitzung 06: Hochschuldidaktik: Wie halte ich einen guten Vortrag? Anke Diez
13.06. Sitzung 07: Mengen, Funktionen, und die Kontinuumshypothese Rob van Stee
20.06. Sitzung 08: Ein Lob der Ungleichungen (14:00 Uhr! SR 131) Peter Sanders
27.06. Sitzung 09: Schubfachprinzip und doppeltes Abzählen Peter Sanders
04.07. Sitzung 10: Cayleys Formel für die Anzahl der Bäume Marc Benkert
11.07. Sitzung 11: Ein Fünf-Farben-Satz & Die Museumswächter Marc Benkert
18.07. Sitzung 12: Von Freunden & Politikern, Das Nadel-Problem v. Buffon (SR -101!) Martin Nöllenburg
25.07. Sitzung 13: Die Probabilistische Methode Peter Sanders

Literatur

  1. Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK. Dritte Auflage, Springer Verlag, 2003.
  2. Martin Aigner and Günter M. Ziegler. Das BUCH der Beweise. Zweite Auflage, Springer Verlag, 2003.