Reconstructing Colourings of Finite Groups

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

Aachen (2017)
Dissertation / PhD Thesis

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.

Institutions

• Department of Mathematics [110000]
• Chair of Mathematics II (for Engineers) [113210]