On the reconstruction index of permutation groups: semiregular groups. (Q1861179)

Let \(G\) be a permutation group on the set \(\Omega\). \(G\) has also a natural action on the set of subsets of \(\Omega\). Two such subsets \(\Delta\), \(\Gamma\) will be called `isomorphic' if they are in the same \(G\)-orbit, and will be called `hypomorphic' if there exists a bijection \(h\colon\Delta\to\Gamma\) so that for all \(\delta\in\Delta\) we have that \(\Delta\setminus\{\delta\}\) is isomorphic to \(\Gamma\setminus\{h(\delta)\}\). Then \(\Delta\) is `reconstructible' if all sets hypomorphic to \(\Delta\) are isomorphic to \(\Delta\). The `reconstruction index' is the least integer \(r\) so that every finite subset of \(\Omega\) of \(r\) or more elements is reconstructible. The authors determine the reconstruction index for all semiregular permutation groups (finite or infinite). It turns out that this index is \(3\), \(4\), or \(5\). The reconstruction problem formulated in terms of permutations groups, like done in this paper, is closely related to classical reconstruction problems, like the reconstructability of a graph from the isomorphism classes of its vertex (or edge) deleted subgraphs.