The \(k\)-orbit reconstruction and the orbit algebra (Q1201909)

The main achievement of this paper is a unified presentation of several well-known reconstruction problems in the single framework of an orbit reconstruction problem: If \(G\) is a permutation group acting on a finite set \(W=\{w_ 1,w_ 2,\dots,w_ n\}\) it has a natural action on the Boolean algebra \({\mathcal B}_ n\) of all subsets \(c_ j\), \(1\leq j\leq 2^{n-1}\), of \(W\), defined by \(C^ g_ j=\{w_{\alpha_ 1},w_{\alpha_ 2},\dots,w_{\alpha_ k}\}^ g=\{w^ g_{\alpha_ 1},w^ g_{\alpha_ 2},\dots,w^ g_{\alpha_ k}\}\) for all \(g\in G\). If \(h_ i=\{c_ 1^{(i)},c_ 2^{(i)},\dots,c^{(i)}_{z(i)}\}\) is an orbit of \((G,{\mathcal B}_ n)\), all \(c^{(i)}_ j\)'s in it have the same cardinality \(m(i)\) (the arity of \(h_ i\)). If \(m(i)=k\), \(h_ i\) is called a \(k\)-orbit of \((G,{\mathcal B}_ n)\). The subsets \(c_ j\) can be thought of as the basis elements of a \(2^ n\)-dimensional vector space \(C\) over a field \(F\), which can be converted into an algebra through the multiplication \(c_ ic_ j=c_ i\cup c_ j\). The subalgebra \(C^ G=\{s\in C| s^ g=s\) for all \(g\in G\}\) of elements of \(C\), invariant under the group action, is an associative and commutative algebra over \(F\) with the set of elements \(h_ i=c_ 1^{(i)}+c_ 2^{(i)}+\cdots+c^{(i)}_{z(i)}\), \(0\leq i\leq N\), forming a basis. This is called the orbit algebra of \(G\). Let \(c_ p^{(i)}=\{w_{\alpha_ 1},w_{\alpha_ 2},\dots,w_{\alpha_ k}\}\) be an arbitrary element of the \(k\)-orbit \(h_ i\). Each element \(c_ p^{(i)}\backslash\{w_{\alpha_ q}\}\) of the multiset \(\langle c_ p^{(i)}\backslash\{w_{\alpha_ 1}\}\), \(c_ p^{(i)}\backslash\{w_{\alpha_ 2}\},\dots,c_ p^{(i)}\backslash\{w_{\alpha_ k}\}\rangle\) is a \((k-1)\)-subset which is a member of a unique \((k-1)\) orbit \(h^ q_ i\). The multiset \(H(h_ i)=\langle h_ i^{(1)},h_ i^{(2)},\dots,h_ i^{(k)}\rangle\) of maximal suborbits of \(h_ i\) can be called the deck of \(h_ i\). Two orbits \(h_ i\) and \(h_ j\) are defined to be equivalent if \(H(h_ i)=H(h_ j)\) and \(h_ i\) is said to be reconstructable if it is equivalent only to itself. The orbit reconstruction problem asks for necessary and sufficient conditions for reconstructibility of \(k\)-orbits. The author defines the reconstruction index of \(G\) as the integer \(\rho(G)\) such that all \(k\)-orbits of \(G\) with \(k>\rho(G)\) are reconstructible, whereas not all \(\rho(G)\) orbits are reconstructible. The author formulates several known reconstruction problems as orbit reconstruction problems. For example, when \(G\) is the pair symmetric group \(S_ n^{(2)}\) acting on \(W^{(2)}\), the 2-element subsets of \(W\), thought of as the edges of the complete graph \(K_ n(W,W^{(2)})\), the orbit reconstruction problem is the edge reconstruction problem for graphs and here the conjecture is that \(\rho(G)=3\). The author obtains generalizations of the results of Lovász and Müller in this regard. An orbit invariant of the permutation group \(G=(G,W)\) is a function \(u:{\mathcal B}\to F\) taking constant values on the orbits \(h_ i\). The author defines a polynomial algebra \(A^ G\), something like a dual to \(C^ G\), called the co-orbit algebra and shows that its elements constitute all the orbit invariants of \(G\). A set of invariants is called complete if any two orbits are distinguished by some invariant of the set. An important result obtained is that a set of invariants is complete if and only if it generates the co-orbit algebra. The study makes substantial contact with the works of a wide spectrum of researchers in reconstruction and invariant theory.