Informationen zum

240231 Bachelorseminar zur Kombinatorik und Gruppentheorie

von Ph. Lampe, Sommersemester 2013.

Termin: Dienstag, 8-10 Uhr, Raum C0-281.
Eintrag im elektronischen Vorlesungsverzeichnis.


Vorbesprechung

Am Donnerstag, den 31.01.2013, um 14:00 Uhr in V5-227.
Interessenten, die nicht zur Vorbesprechung kommen konnten, mögen bitte Kontakt mit dem Organisator aufnehmen.


Beschreibung

In diesem Seminar möchten wir schwierige kombinatorische Probleme mit Hilfe der Gruppentheorie lösen. Im Mittelpunkt steht Pólyas Theorie der Zyklenzeiger. Sie ist nach dem ungarischen Mathematiker George Pólya (1887-1985) benannt.

In diesem Seminar möchten wir kombinatorischen Fragen wie der Folgenden nachgehen: Auf wie viele Arten können wir die sechs Seitenflächen eines Würfels färben, wenn wir 2 (oder allgemeiner 3, 4, 5, ...) Farben zur Verfügung haben? Ist der Würfel im Raum fixiert, so gibt es 26 (bzw. 36, 46, 56, ...) Färbungen, da jede Seite 2 (bzw. 3,4,5,...) Farben annehmen kann. Nun möchten wir aber solche Färbungen identifizieren, die durch eine Drehbewegung im Raum ineinander überführt werden.

Wie sich herausstellt, hilft die Gruppentheorie dabei, solche Fragestellungen zu beantworten. Den Begriff der Gruppen haben die die Mathematiker Évariste Galois (1811-1832) und Niels Henrik Abel (1802-1829) eingeführt. Gruppen beschreiben oft die Symmetrien eines Objekts. Die Gruppentheorie hat zahlreiche Anwendungen. Die wichtigsten Beispiele sind Nichtlösbarkeitsbeweise polynomieller Gleichungen und geometrischer Konstruktionen. In dem Seminar möchten die Gruppentheorie anwenden, um kombinatorische Aufgaben zu effektiv zu lösen. In dem Zusammenhang sind Zykel von Gruppenwirkungen von Bedeutung.



Kommen wir zurück zu dem konkreten Beispiel. Wir bezeichen die Vorderseite des Würfels (also das Quadrat 1265) mit A. Entsprechend seien B die Rückseite, C und D die linke bzw. rechte Seitenfläche und E und F die untere bzw. obere Seite. Wir ordnen jeder Drehung ein Monom in den Variablen z1, z2, z3, ... zu. Der Exponent von zi ist dabei die Anzahl der Zykeln der Länge i. Die folgenden 24 Drehungen führen den Würfel in sich selbst über:

  • Die 6 Drehungen um 90° bzw. -90° um die drei Achsen, die jeweils mittig und rechtwinklig durch gegenüberliegende Seitenflächen gehen. Für die Drehung um die Achse durch die Mittelpunkte von Ober- und Unterseite beispielsweise gibt es 2 Zykel E→E und F→F der Länge 1 (gegeben durch beiden festgelassenen Seitenflächen) und 1 Zykel C→A→D→B→C der Länge 4. Wir erhalten das Monom 6z12z41.
  • Die 3 Drehungen um 180° um die drei Achsen, die jeweils mittig und rechtwinklig durch gegenüberliegende Seitenflächen gehen. Für die Drehung um die Achse durch die Mittelpunkte von Ober- und Unterseite beispielsweise gibt es 2 Zykel E→E und F→F der Länge 1 (gegeben durch beiden festgelassenen Seitenflächen) und 2 Zykel A→ B→A und C→ D→C der Länge 2. Wir erhalten das Monom 3z12z22.
  • Die 8 Drehungen um 120° bzw. 240° um die vier Raumdiagonalen. Für die Drehung um die Raumdiagonale 17 beispielsweise gibt es 2 Zykel A→ F→ C→A und D→ B→ E → D der Länge 3. Wir erhalten das Monom 8z32.
  • Die 6 Drehungen um 180° um die sechs Geraden durch die Mittelpunkte gegenüberliegender Kanten. Für die Drehung um die Gerade durch die Mittelpuknte von 23 und 58 beispielsweise gibt es 3 Zykel C→ F→ C, D→ E→ D und A→ B→ A der Länge 2. Wir erhalten das Monom 6z23.
  • Die identische Abbildung mit 6 Zykeln der Länge 1. Wir erhalten das Monom z16.

  • Der Zyklenzeiger ist nun die Summe all dieser Monome dividiert durch die Gesamtzahl 24 an Symmetrien: Z(z1,z2,z3,z4)=124(z16+6z12z4+3z12z22+8z32+6z23). Der Satz von Pólya sagt in diesem Fall: die Anzahl der Färbungen eines Würfels mit n Farben ist Z(n,n,n,n)=124(n6+3n4+12n3+8n2). Für n=2 (oder 3,4,5, ...) erhalten wir speziell 10 (bzw. 57, 240, 800, ...) Färbungen.

    In dem Seminar möchten zunächst relevante Begriffe aus der Gruppentheorie wiederholen und einführen. Eine besondere Rolle spielt dabei das Lemma von Burnside. Dann formulieren und beweisen wir den Satz von Pólya in voller Allgemeinheit. Der Kern des Seminars bilden weitere Anwendungen des Satzes, die wir in einzelnen Vorträgen im Detail vorstellen. Oft besteht ein Bezug zur Zahlentheorie.

    Vorkenntnisse

    Das Seminar wendet sich an Studentinnen und Studenten mit Interesse an kombinatorischen Fragestellungen und dem Willen, sich in ein neues Thema einzuarbeiten. Kenntnisse der Vorlesung 240216 Vertiefung Gruppentheorie oder einer ähnlichen Veranstaltung sind hilfreich, aber nicht notwendig.


    Vortragsbeschreibungen

    Eine Beschreibung der Vorträge finden Sie hier.


    Literatur

    Hier finden Sie die zu verwendende Literatur. Rot gekennzeichnet ist die Originalarbeit von George Pólya, auf der die Theorie der Zyklenzeiger beruht.

    [A] M. Aigner: Diskrete Mathematik.
    Vieweg, 5. Auflage, 2004.
    [D] R. Diestel: Graphentheorie.
    Springer, 2. Auflage, 2000.
    [G] J. Gallian: Weird Dice.
    Math Horizons, 1995, S. 31-32.
    [GKP] R. Graham, D. Knuth, O. Patashnik: Concrete Mathematics: A Foundation for Computer Science.
    Addison Wesley Publishing Company, 1994.
    [H1] I. Hachtel: Der Zyklenzeiger einer Gruppe.
    Der mathematische und naturwissenschaftliche Unterricht (MNU) 47, S. 467-471, 1984.
    [H2] I. Hachtel: Kombinatorik und Gruppentheorie.
    Mathe ist cool!, Cornelsen Verlag, 2001.
    [J1] M. Jeger: Einführung in Kombinatorik, Band 1.
    Ernst Klett Verlag, 1973.
    [J2] M. Jeger: Einführung in Kombinatorik, Band 2.
    Ernst Klett Verlag, 1973.
    [K] K. Keeler: Futurama theorem.
    http://theinfosphere.org/Futurama_theorem.
    [P] G. Pólya: Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen.
    Acta Mathematica 68, S. 145-254, 1937.
    [Pr] V. Prasolov: Essays on numbers and figures.
    American Mathematical Society, 2000.
    [R] H. Reeker: Lateinische Quadrate.
    Mathe ist cool!, Cornelsen Verlag, 2001.
    [Sch] R.H. Schulz: Codierungstheorie: Eine Einführung.
    Vieweg Verlag, 2003.
    [S] H. Siemon: Anwendungen der elementaren Gruppentheorie.
    Klett Studienbücher, 1984.
    [T] T. Tao: Structure and Randomness: pages from year one of a mathematical blog.
    American Mathematical Society, 2008.
    [V] J. Verhoeff: Error Detecting Decimal Codes.
    Mathematical Centre Tracts, 1969.


    Liste der Termine

    Datum # Thema Sprecher(in)
    9. April 1 Das chromatische Polynom eines Graphen und der Satz von Whitney Helena Röhling
    23. April 2 Zagiers kombinatorischer Beweis des Zweiquadratesatzes Timm Polikeit
    30. April 3 Der Satz von Keeler Jens Lichtenstein
    14. Mai 4 Der Satz von Pólya und die Enumeration verschiedener Würfelfärbungen Nicola Friedrichs
    21. Mai 5 Der Zyklenzeiger einer Permutationsgruppe und Abzählprobleme Adam Bartkowiak
    28. Mai 6 Das Lemma von Burnside Philipp Krüer
    4. Juni 7 Abzählende Potenzreihen und der Crazy Dice Hanna Olszański
    11. Juni 8 Abzählprobleme aus der Graphentheorie Annecarin Milden
    18. Juni 9 Abzählprobleme aus der Chemie Clarissa Neugebauer
    25. Juni 10 Lateinische und magische Quadrate Kristina Regehr
    2. Juli 11 Fehler erkennende Prüfsummen vermöge der Diedergruppe Imke Clifton
    9. Juli 12 Die Kreuzungszahl eines Graphen Jannik Sender