Reconstructing infinite objects
type: Item
instance of: scholarly article
title: Reconstructing infinite objects
zbMATH Open document ID: 1036.05033
DOI: 10.1016/S0012-365X(01)00427-7
author: Dieter Rautenbach
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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\…
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 1792390
zbMATH Keywords: reconstruction
zbMATH Keywords: isomorphism
zbMATH Keywords: automorphism
reviewed by: Robert R. Molina
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1792390