Conjecture on reconstruction from transposition-neighborhoods

At least 18 years old · documented by

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

N(Sym⁡n(T),r)=N2(Sym⁡n(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.