UNITARY TORIC CLASSES, THE REALITY AND DESIRE DIAGRAM, AND SORTING BY TRANSPOSITIONS

H. Eriksson et al. made a breakthrough to the problem of sorting by transpositions by proposing a quotient structure named toric graph, which allowed the reduction of the search space, establishing the transposition diameter D(t)(n) = left perpendicular n+1/2 right perpendicular broken vertical bar 1, for the cases n = 13 and n = 15, and invalidating a conjecture by J. Meidanis, M. E. M. T. Walter, and Z. Dias that the transposition diameter would be equal to the transposition distance of the reverse permutation left perpendicular n/2 right perpendicular + 1. I. Elias and T. Hartman extended the lower bound D(t)(n) >= left perpendicular n+1/2 right perpendicular + 1, to all odd values of n, n >= 13. The value n = 15 is the largest for which D(t)(n) is known. The goal of the present paper is to further study the toric graph, focusing on the case when n + 1 is prime, providing positive evidence that J. Meidanis, M. E. M. T. Walter, and Z. Dias's conjecture is still valid when n is even. We show that, when n + 1 is prime, the properties of the reverse permutation are shared by permutations that fall into unitary toric classes; we prove that their reality and desire diagrams have just one cycle, consequently proving that those permutations are separated by at least n/2 transpositions among themselves, and we show that there are at least two permutations whose transposition distance is n/2 and two permutations, other than the reverse, whose distance is at least n/2 + 1, with respect to the identity.