h1

000698365 001__ 698365
000698365 005__ 20230408005305.0
000698365 0247_ $$2HBZ$$aHT019431438
000698365 0247_ $$2Laufende Nummer$$a36477
000698365 0247_ $$2datacite_doi$$a10.18154/RWTH-2017-07674
000698365 037__ $$aRWTH-2017-07674
000698365 041__ $$aEnglish
000698365 082__ $$a510
000698365 1001_ $$0P:(DE-82)699954$$aSimon, Jan$$b0
000698365 245__ $$aReconstructing Colourings of Finite Groups$$cvorgelegt von Jan Simon, M. Sc.$$honline
000698365 260__ $$aAachen$$c2017
000698365 300__ $$a1 Online-Ressource (142 Seiten) : Illustrationen
000698365 3367_ $$02$$2EndNote$$aThesis
000698365 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000698365 3367_ $$2BibTeX$$aPHDTHESIS
000698365 3367_ $$2DRIVER$$adoctoralThesis
000698365 3367_ $$2DataCite$$aOutput Types/Dissertation
000698365 3367_ $$2ORCID$$aDISSERTATION
000698365 502__ $$aDissertation, RWTH Aachen University, 2017$$bDissertation$$cRWTH Aachen University$$d2017$$gFak01$$o2017-06-23
000698365 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000698365 5203_ $$aDiese 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.$$lger
000698365 520__ $$aThis 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.$$leng
000698365 588__ $$aDataset connected to Lobid/HBZ
000698365 591__ $$aGermany
000698365 653_7 $$acombinatorics
000698365 653_7 $$adeck
000698365 653_7 $$afinite groups
000698365 653_7 $$areconstruction
000698365 7001_ $$0P:(DE-82)IDM00098$$aTriesch, Eberhard$$b1$$eThesis advisor$$urwth
000698365 7001_ $$0P:(DE-82)004372$$aRautenbach, Dieter$$b2$$eThesis advisor
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.pdf$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365_source.zip$$yRestricted
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.gif?subformat=icon$$xicon$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.jpg?subformat=icon-1440$$xicon-1440$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.jpg?subformat=icon-640$$xicon-640$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000698365 8564_ $$uhttps://publications.rwth-aachen.de/record/698365/files/698365.pdf?subformat=pdfa$$xpdfa$$yOpenAccess
000698365 909CO $$ooai:publications.rwth-aachen.de:698365$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
000698365 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000698365 9141_ $$y2017
000698365 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00098$$aRWTH Aachen$$b1$$kRWTH
000698365 9201_ $$0I:(DE-82)113210_20140620$$k113210$$lLehrstuhl II für Mathematik (für Ingenieure)$$x0
000698365 9201_ $$0I:(DE-82)110000_20140620$$k110000$$lFachgruppe Mathematik$$x1
000698365 961__ $$c2017-10-02T08:18:18.090237$$x2017-08-22T19:32:36.985191$$z2017-10-02T08:18:18.090237
000698365 9801_ $$aFullTexts
000698365 980__ $$aI:(DE-82)110000_20140620
000698365 980__ $$aI:(DE-82)113210_20140620
000698365 980__ $$aUNRESTRICTED
000698365 980__ $$aVDB
000698365 980__ $$aphd