Reconstructing infinite objects
The most familiar topics in the area of reconstruction are the famous graph reconstruction conjectures which state that a graph with at least three vertices (four edges) is determined up to isomorphism by its collection of vertex (edge) deleted subgraphs. Interest in these two conjectures has led to the investigation of more general reconstruction problems. The main theorem of this paper can be used to show that a wide variety of objects are reconstructible. This theorem is a generalization of an algebraic reconstruction theorem due to \textit{N. Alon} et al. [J. Comb. Theory, Ser. B 47, 153--161 (1989; Zbl 0633.05050)]. Let \(G\) be a group of automorphisms of a set \(X\). If \(Y\subseteq X\), let \(g(Y)=\{g(y)\mid y\in Y\}\) and define the orbit of \(Y\) to be the set \(G(Y)=\{g(Y)\mid g\in G\}\). Let \(R\) be a set of representatives for the family of all such orbits. Two sets \(Y,Y'\subseteq X\) are isomorphic if \(G(Y)=G(Y')\). For \(k\geq 1\) the \(k\)-deck of \(Y\) is defined as the mapping \(d_{Y,k}\) defined on \(R\) such that for each \(r\in R\), \(d_{Y,k}(r)\) is the number of subsets of \(Y\) of cardinality \(k\) that are isomorphic to \(r\). We say that \(Y\) is \(k\)-reconstructible if it is determined up to isomorphism by its \(k\)-deck. The main result of this paper can be stated as follows: Let \(1\leq \widetilde k\leq k\) be integers. Let \(G\) be a group of automorphisms of a set \(X\). Let \(Y\) and \(Y'\) be (possibly infinite) subsets of \(X\) of cardinality \(| Y| \), \(| Y'| >k\) that are not \(G\)-isomorphic and such that \(d_{Y,l}=d_{Y',l}\) for all \(k'\leq l\leq k\). Let the \(\widetilde k\)-deck of \(Y\) take only finite values. Let \(S\) be a subset of \(Y\) of cardinality \(| S| =\widetilde k\) with finite stabilizer \(| G_S| <\infty\). Then either there is a finite set \(T\) of cardinality \(| T| \geq k+1\) with \(S\subseteq T\subseteq Y\) and some \(\varepsilon\in\{0,1\}\) such that for every set \(K\) with \(S\subseteq K\subseteq T\) and \(| K| =\varepsilon \pmod 2\), there is a \(g\in G\) with \(T\cap g(Y)=K\), or \(d_{Y,| A| }(A)=d_{Y',| A| }(A)\) for all finite sets \(A\) with \(S\subseteq A\subseteq Y\). As an application, the author applies this result to the problem of reconstructing infinite point sets in \( R^n\) up to isomorphism with respect to two different groups of automorphisms.
scientific article; zbMATH DE number 1792390