Reconstructing Colourings of Finite Groups

Simon, Jan; Triesch, Eberhard; Rautenbach, Dieter

doi:10.18154/RWTH-2017-07674

Reconstructing Colourings of Finite Groups

Simon, Jan

2017

Verantwortlichkeitsangabevorgelegt von Jan Simon, M. Sc.

ImpressumAachen 2017

Umfang1 Online-Ressource (142 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2017

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)^RWTH* ; Rautenbach, Dieter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2017-06-23

Online
DOI: 10.18154/RWTH-2017-07674
URL: https://publications.rwth-aachen.de/record/698365/files/698365.pdf
URL: https://publications.rwth-aachen.de/record/698365/files/698365.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
combinatorics (frei) ; deck (frei) ; finite groups (frei) ; reconstruction (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

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.

This thesis strives to promote a consistently combinatorial approach to study reconstruction problems on finite groups and $G$-sets. At the centre of this endeavour is the notion of the combinatorial $k$-deck coming in its two flavours for colourings and subsets. The combinatorial $k$-deck of a colouring $c$ of a finite $G$-set $X$ is defined as the multiset of equivalence classes of restrictions of $c$ to $k$-element subsets of $X$ (the so-called $k$-patches) that are moved around by the action of $G$, thus providing the notion of equivalence. Put another way, the combinatorial $k$-deck counts, for each $k$-patch, how many equivalent copies of it appear in $c$. The dominating notion of $k$-deck in the literature is a bit different: There, arithmetic calculations with the "colours" (that are indeed numbers) are performed resulting in analytic expressions satisfying certain invariance properties. The name analytical $k$-deck (as opposed to the combinatorial $k$-deck) is suggested and consistently used here. The combinatorial $k$-deck always determines the analytical $k$-deck. Conversely, the colour set $F$ and the analytical $\bigl((|F|-1)k\bigr)$-deck together determine the combinatorial $k$-deck provided that $F\subseteq\mathbb{R}_{\geq 0}$. The gap between the smallest $k_1$ for which the combinatorial $k_1$-deck is able to distinguish between two given colourings and the smallest $k_2$ for which the analytical $k_2$-deck is able to do so may become arbitrarily large - even after a suitable change of colour values in favour of the analytical deck (whose reconstruction qualities are sensitive to the choice of the colour values). However, even for the combinatorial deck there is no global reconstruction number $k_0\in\mathbb{N}$, such that for all finite groups $G$, all finite $G$-sets $X$ and all (finite) colour sets $F$ each colouring $c:X\longrightarrow F$ is reconstructible from its combinatorial $\operatorname{min}\{k_0,|X|\}$-deck. It is unknown whether there is a global subset reconstruction number for all finite groups. In this respect the 5-transitive Mathieu groups $M_{12}$ and $M_{24}$ show that such a global subset reconstruction number would have to be at least 6. A full combinatorial understanding of all 3-deck failures of subsets in cyclic groups up to (and including) order 24 is obtained, mainly by considering so-called self-complementary subsets $A\subseteq G$ for which there is some $g\in G$ with $gA=G\smallsetminus A$. Self-complementary subsets also explain a great amount of 3-deck failures in dicyclic groups. This thesis contains several positive reconstruction results, too. While the focus in the literature was so far mainly on cyclic or Abelian groups, the techniques suggested here are, in principle, applicable to all finite groups. One of them is the method of anchors, where the merits of sticking consistently to the combinatorial approach become particularly evident. Anchors show, for instance, that a colouring of a finite group with non-empty colour class $A$ is reconstructible from the combinatorial $\left(\left\lfloor\operatorname{log}_2 |A|\right\rfloor+2\right)$-deck. (This was previously shown for subsets but the proof was more involved.) Another way to obtain positive reconstruction results (for the 3-deck only) is by means of certain matrices derived from the group matrix. The approach is a generalization of an idea which was previously applied to cyclic groups only. Applications include results for certain dihedral groups and for $p$-groups. One if these results is the following one: If $G$ is a finite $p$-group of order $|G|\geq 3$ and $A\subseteq G$ with $p\nmid|A|$ then any colouring of $G$ with one of its colour classes equal to $A$ is reconstructible from the 3-deck.

OpenAccess:
PDF PDF (PDFA)
(additional files)