NDLI: Unitary Toric Classes, the Reality and Desire Diagram, and Sorting by Transpositions

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kowada, Luis Antonio B. Faria, Luerbio de A. Hausen, Rodrigo de Figueiredo, Celina M. H.
Copyright Year	2010
Abstract	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)=\lfloor\frac{n+1}{2}\rfloor+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 $\lfloor n/2\rfloor+1$. I. Elias and T. Hartman extended the lower bound $D_t(n)\geq\lfloor\frac{n+1}{2}\rfloor+1$, to all odd values of n, $n\geq13$. 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.
Starting Page	792
Ending Page	807
Page Count	16
File Format	PDF
ISSN	08954801
DOI	10.1137/08074413X
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	24
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2010-07-08
Access Restriction	Subscribed
Subject Keyword	sorting by transpositions Computational difficulty of problems reality and desire diagram breakpoint graph genome rearrangements Protein sequences, DNA sequences toric permutation Searching and sorting Combinatorics on words Group actions on combinatorial structures Problems related to evolution Permutations, words, matrices
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Advancing the Transposition Distance and Diameter through Lonely Permutations

Sorting Strings by Reversals and by Transpositions

Multiset permutation generation by transpositions

Permutations as Product of Parallel Transpositions

Reversals and Transpositions Over Finite Alphabets

Approximation Algorithms for Genome Rearrangements (sorting Signed Permutations by Reversals and Transpositions)

Representing Permutations with Few Moves

Symmetric Permutations Avoiding Two Patterns

Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions

Unitary Toric Classes, the Reality and Desire Diagram, and Sorting by Transpositions

Similar Documents

Advancing the Transposition Distance and Diameter through Lonely Permutations

Sorting Strings by Reversals and by Transpositions

Multiset permutation generation by transpositions

Permutations as Product of Parallel Transpositions

Reversals and Transpositions Over Finite Alphabets

Approximation Algorithms for Genome Rearrangements (sorting Signed Permutations by Reversals and Transpositions)

Representing Permutations with Few Moves

Symmetric Permutations Avoiding Two Patterns

Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions

Unitary Toric Classes, the Reality and Desire Diagram, and Sorting by Transpositions