Einführung in die Kombinatorik

Dieter Jungnickel

• Verlag: De Gruyter
• Jahr: 2008
• eBook-ISBN: 9783110197990
• Auflage: 1
• Thema: Mathematics
• Thema: Mathematics General

Ziel dieser vollständig überarbeiteten und erweiterten Neuauflage ist es, eine weitgehend elementare Einführung in ausgewählte Teile der Kombinatorik zu geben. Dabei wird stets versucht, nicht nur die Grundlagen darzustellen, sondern auch in jedem Kapitel exemplarisch einige tiefer liegende Resultate vollständig zu beweisen.

Highlights sind:

• allgemeine Lösung des Kirkmanschen Schulmädchenproblems und mehr über Blockpläne
• projektive Ebenen und Räume, einschließlich des Freundschaftstheorems
• Anwendungen in der Kryptographie, Authentikation von Nachrichten, Zugangskontrolle zu geheimen Informationen
• Heiratssatz und eine Fülle verwandter Sätze, etwa über Flüsse auf Netzwerken
• allgemeine Widerlegung der Eulerschen Vermutung über Paare orthogonaler lateinischer Quadrate
• der Satz vom Diktator
• verblüffende Eigenschaften der Morse-Thue-Folge
• einige Perlen aus der Codierungstheorie, inklusive konkreter Anwendungen etwa bei Prüfziffersystemen
• der klassische Satz von Ramsey und verwandte Ergebnisse
• Partitionen und Abzählen, etwa das klassische Menage-Problem
• Endliche Geometrie und Graphentheorie, insbesondere ein kurzer Beweis des Fünffarbensatzes und das Königsberger Brückenproblem

Das Buch wendet sich an Dozenten, die eine entsprechende Vorlesung über Kombinatorik halten, sowie an Studenten der Mathematik, denen das Buch als Begleitlektüre zu einer solchen Vorlesung oder zum Selbststudium dienen kann. Angesprochen sind auch Lehrer und Schüler in der gymnasialen Oberstufe, die im Rahmen eines Leistungskurses erste Einblicke in die reizvollen und teilweise sehr direkten Fragestellungen der Kombinatorik gewinnen wollen.

Inhaltsverzeichnis

• I Das kleine Einmaleins der Kombinatorik
• 1 Mengen
• 2 Einfache Anzahlaussagen
• 3 Das Inklusions-Exklusions-Prinzip
• 3.1 Das Inklusions-Exklusions-Prinzip mit Gewichten
• 3.2 Zahlentheoretische Anwendungen der Siebformel
• 3.3 Das Problème des ménages
• 3.4 Permanenten
• II Der Heiratssatz und seine Verwandten
• 1 Der Heiratssatz
• 2 Zum Heiratssatz verwandte Sätze
• 2.1 Die Sätze von König und Dilworth
• 2.2 Die Äquivalenz des Heiratssatzes mit den Sätzen von König und Dilworth
• 2.3 Verwandte Ergebnisse
• 2.4 Der Satz von Menger
• 3 Das Schnitt-Fluß-Theorem von Ford und Fulkerson
• 3.1 Gerichtete Graphen und Fluß-Netzwerke
• 3.2 Flußmaximierung
• 3.3 Flüsse, Matchings und disjunkte Wege
• 3.4 Der Satz von Baranyai
• III Orthogonale lateinische Quadrate
• 1 Problemstellung und Historisches
• 2 Grundbegriffe und erste Existenzaussagen
• 3 Endliche Körper
• 4 Der Satz von MacNeish
• 5 Differenzmatrizen
• 6 Widerlegung der Eulerschen Vermutung
• 7 Eine Anwendung: Authentikationscodes
• IV Der Satz vom Diktator
• 1 Problemstellung
• 2 Mächtige Familien
• 3 Auswege
• V Fastperiodische 0-1-Folgen
• 1 Die Morse-Thue-Folge
• 2 Fastperiodizität
• VI Der Satz von Ramsey
• 1 Die finite Version des Satzes von Ramsey
• 2 Die unendliche Version des Satzes von Ramsey
• VII Der Satz von van der Waerden
• 1 Arithmetische Progressionen
• 2 Beweis des Satzes von van der Waerden
• 3 Der Satz von Szemerédi
• 4 Ergebnisse von Schur, Rado und Deuber
• 5 Der Satz von Hales und Jewett
• VIII Codes
• 1 Sofort bzw. eindeutig entzifferbare Codes
• 2 Prüfziffersysteme
• 3 Fehlerkorrigierende Codes
• 4 Lineare Codes
• 5 Zyklische Codes und Polynomideale
• 6 BCH-Codes
• 7 Bemerkungen zur Implementierung
• IX Endliche projektive Ebenen und Räume
• 1 Grundlagen
• 2 Existenzfragen
• 3 Polaritäten
• 4 Das Freundschaftstheorem
• 5 Kollineationen und der Satz von Singer
• 6 Bögen und MDS-Codes
• 7 Unterebenen und Blockademengen
• 8 Anwendungen in der Kryptographie
• 9 Affine Geometrien
• X Blockpläne
• 1 Grundlagen
• 2 Direkte Konstruktionen
• 3 GDDs
• 4 Relative Differenzfamilien
• 5 Der PBD-Hüllenoperator
• 6 Blockpläne mit k ≤ 5
• 7 Auflösbare Blockpläne
• XI Symmetrische Blockpläne und Differenzmengen
• 1 Symmetrische Blockpläne: Grundlagen
• 2 Der Satz von Bruck, Ryser und Chowla
• 3 Hadamardmatrizen und Blockpläne
• 4 Eine rekursive Konstruktion
• 5 Differenzmengen und Gruppenringe
• 6 Multiplikatoren
• 7 Der Mann-Test
• 8 Planare Differenzmengen
• 9 Die Hadamardsche Ungleichung
• XII Partitionen
• 1 Formale Potenzreihen
• 2 Erzeugende Funktionen von Partitions-Anzahlen
• 3 Eulers Pentagonalzahlen-Theorem
• XIII Die Abzähltheorie von Pólya
• 1 Der Zyklenindex einer Permutationsgruppe
• 2 Das Lemma von Burnside
• 3 Der Satz von Pólya
• 4 Bäume und Strünke
• 5 Alkohole
• 6 Die Anzahl der Bäume auf n Punkten
• XIV Kombinatorische Betrachtungen topologischen Ursprungs
• 1 Das Königsberger Brückenproblem
• 2 Der Eulersche Polyedersatz
• 3 Der Fünffarbensatz
• 4 Hamiltonsche Kreise
• 5 Das Spernersche Lemma
• 6 Der Satz von Helly
• XV Spiele auf Graphen
• 1 Baumspiele
• 2 Das klassische Nim-Spiel
• 3 Spiele vom Typ Nim auf Graphen
• XVI Spezielle Folgen von ganzen Zahlen
• 1 Die Fibonacci-Zahlen
• 2 Die Ménage-Zahlen
• 3 Die Rencontres-Zahlen
• 4 Die Partitionszahlen
• 5 Die Catalan-Zahlen
• 6 Die Bell-Zahlen
• 7 Die Stirling-Zahlen zweiter Art
• 8 Die Stirling-Zahlen erster Art
• 9 Die Gauß-Koeffizienten
• Nachwort
• Literaturverzeichnis
• Index