Conjecture on reconstruction from transposition-neighborhoods

From papers

Let G=SymnG=\operatorname{Sym}_n and let TT be the set of transpositions, so that Symn(T)\operatorname{Sym}_n(T) is the corresponding Cayley graph, Br(σ)B_r(\sigma) denotes the radius-rr ball about σ\sigma, and N(Symn(T),r)N(\operatorname{Sym}_n(T),r) and N2(Symn(T),2)N_2(\operatorname{Sym}_n(T),2) are the reconstruction parameters defined in the paper. For any π(1n331)G\pi\in (1^{n-3}\,3^1)^G, any r1r\geq 1, and n2r+1n\geq 2r+1, the reconstruction conjecture asserts that

N(Symn(T),r)=N2(Symn(T),2)=Br(I)Br(π).N(\operatorname{Sym}_n(T),r)=N_2(\operatorname{Sym}_n(T),2)=\lvert B_r(I)\cap B_r(\pi)\rvert.

This generalizes the preceding theorem and corollary on reconstruction of permutations from transposition-neighborhoods, predicting that the relevant reconstruction number is independent of the chosen element of the indicated conjugacy class and equals the intersection size of the two radius-rr balls. The parser supplies no evidence that the conjecture has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Elena Konstantinova, Vladimir Levenshtein and Johannes Siemons, “Reconstruction of permutations distorted by single transposition errors”, arXiv:math/0702191 (2007).

Solutions 0

No solutions have been posted yet.