Reconstructing Colourings of Finite Groups

Simon, Jan; Triesch, Eberhard (Thesis advisor); Rautenbach, Dieter (Thesis advisor)

Aachen (2017)
Doktorarbeit

Dissertation, RWTH Aachen University, 2017

Kurzfassung

Diese Dissertation widmet sich dem Studium von kombinatorischen Rekonstruktionsproblemen auf endlichen Gruppen und $G$-Mengen. Im Zentrum steht der Begriff des kombinatorischen $k$-Decks in seinen beiden Ausprägungen für Färbungen und Teilmengen. Das kombinatorische $k$-Deck einer Färbung $c$ einer endlichen $G$-Menge $X$ ist definiert als die Multimenge der Äquivalenzklassen von Einschränkungen von $c$ auf $k$-elementige Teilmengen von $X$ (den so genannten $k$-Patchs). Der Äquivalenzbegriff wird durch die Gruppenoperation bereit gestellt, mithilfe derer die Gruppe die $k$-Patchs hin und her bewegt. Das kombinatorische $k$-Deck zählt also für jeden $k$-Patch, wie viele äquivalente Kopien von ihm in $c$ vorkommen. Der in der Literatur vorherrschende Deckbegriff für endliche (zumeist Abelsche) Gruppen ist ein bisschen anders: Dort werden die "Farben" (bei denen es sich in Wirklichkeit um Zahlen handelt) zu analytischen Ausdrücken verrechnet, welche gewisse Invarianzeigenschaften erfüllen. Hierfür wird zur Abgrenzung gegenüber dem kombinatorischen $k$-Deck die Bezeichnung analytisches $k$-Deck vorgeschlagen. Während das kombinatorische $k$-Deck immer das analytische $k$-Deck umfasst, legen umgekehrt die Farbmenge $F$ und das analytische $\bigl((|F|-1)k\bigr)$-Deck gemeinsam das kombinatorische $k$-Deck fest, solange $F\subseteq\mathbb{R}_{\geq 0}$ gilt. Die Differenz zwischen dem kleinsten $k_1$, für welches das kombinatorische $k_1$-Deck in der Lage ist zwei gegebene Färbungen zu unterscheiden, und dem kleinsten $k_2$, für welches dies dem analytischen $k_2$-Deck gelingt, kann beliebig groß werden - auch dann, wenn die Farbwerte zugunsten des analytischen Decks abgeändert werden. (Die Rekonstruierbarkeit aus dem analytischen Deck schwankt mit den gewählten Farbwerten.) Allerdings existiert selbst für das kombinatorische Deck keine globale Rekonstruktionszahl $k_0\in\mathbb{N}$ dergestalt, dass für alle endlichen Gruppen $G$, alle endlichen $G$-Mengen $X$ und alle (endlichen) Farbmengen $F$ jede Färbung $c:X\longrightarrow F$ aus dem kombinatorischen $\operatorname{min}\{k_0,|X|\}$-Deck rekonstruierbar ist. Ob eine globale Rekonstruktionszahl für die Rekonstruktion von Teilmengen existiert, ist nicht bekannt. Die 5-transitiven Mathieu-Gruppen $M_{12}$ und $M_{24}$ zeigen jedoch, dass sie, falls dem so ist, nicht kleiner als 6 sein kann. Für zyklische Gruppen bis einschließlich der Ordnung 24 wird eine vollständige (kombinatorische) Erklärung aller Teilmengen, die nicht aus dem 3-Deck rekonstruierbar sind, gegeben. Hierbei spielen selbstkomplementäre Teilmengen eine wesentliche Rolle, d. h. Teilmengen $A\subseteq G$, für die es ein $g\in G$ gibt, sodass $gA=G\smallsetminus A$ gilt. Auch in dizyklischen Gruppen lässt sich das Scheitern des 3-Decks vielfach durch selbstkomplementäre Teilmengen erklären. Diese Arbeit enthält auch eine Reihe positiver Rekonstruktionsergebnisse. Während sich die Literatur bislang hauptsächlich auf Abelsche Gruppen konzentriert hat, sind die hier beschriebenen Methoden im Prinzip auf alle endlichen Gruppen anwendbar. Eine solche Methode, bei der die Vorteile des kombinatorischen Ansatzes besonders deutlich werden, bedient sich so genannter Anker. Mit diesen lässt sich beispielsweise zeigen, dass Färbungen endlicher Gruppen mit einer nicht-leeren Farbklasse $A$ aus dem kombinatorischen $\bigl(\lfloor\operatorname{log}_2 |A|\rfloor+2\bigr)$-Deck rekonstruierbar sind. (Dies wurde zuvor für Teilmengen gezeigt, allerdings mit aufwändigerem Beweis.) Ein anderer Weg zu positiven Rekonstruktionsergebnissen (jedoch nur für das 3-Deck) verläuft über gewisse Matrizen, die in Zusammenhang mit der Gruppenmatrix stehen. Hierbei handelt es sich um die Verallgemeinerung einer Idee, die bislang nur in zyklischen Gruppen angewandt wurde. Anwendungen werden unter anderem für gewisse Diedergruppen und für $p$-Gruppen betrachtet. Zum Beispiel gilt: Ist $G$ eine endliche $p$-Gruppe der Ordnung $|G|\geq 3$ und $A\subseteq G$ eine Teilmenge mit $p\nmid|A|$, so ist jede Färbung von $G$, die $A$ als Farbklasse besitzt, aus dem 3-Deck rekonstruierbar.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehrstuhl II für Mathematik (für Ingenieure) [113210]