% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Simon:698365,
author = {Simon, Jan},
othercontributors = {Triesch, Eberhard and Rautenbach, Dieter},
title = {{R}econstructing {C}olourings of {F}inite {G}roups},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
reportid = {RWTH-2017-07674},
pages = {1 Online-Ressource (142 Seiten) : Illustrationen},
year = {2017},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2017},
abstract = {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.},
cin = {113210 / 110000},
ddc = {510},
cid = {$I:(DE-82)113210_20140620$ / $I:(DE-82)110000_20140620$},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2017-07674},
url = {https://publications.rwth-aachen.de/record/698365},
}
guest ::