Posets and Permutations in the Duplication-Loss Model: Minimal Permutations with d Descents
| dc.creator | Bouvel, Mathilde | |
| dc.creator | Pergola, Elisa | |
| dc.date | 2008-06-09 | |
| dc.date.accessioned | 2026-07-07T12:19:25Z | |
| dc.date.available | 2026-07-07T12:19:25Z | |
| dc.description | In this paper, we are interested in the combinatorial analysis of the whole genome duplication - random loss model of genome rearrangement initiated in a paper of Chaudhuri, Chen, Mihaescu, and Rao in SODA 2006 and continued by Bouvel and Rossin in 2007. In this model, genomes composed of n genes are modeled by permutations of the set of integers [1..n], that can evolve through duplication-loss steps. It was previously shown that the class of permutations obtained in this model after a given number p of steps is a class of pattern-avoiding permutations of finite basis. The excluded patterns were described as the minimal permutations with d=2^p descents, minimal being intended in the sense of the pattern-involvement relation on permutations. Here, we give a local and simpler characterization of the set B_d of minimal permutations with d descents. We also provide a more detailed analysis - characterization, bijection and enumeration - of two particular subsets of B_d, namely the patterns in B_d of size d+2 and 2d. | |
| dc.description | 25 pages 20 figures Soumis a TCS | |
| dc.identifier | https://arxiv.org/abs/0806.1494 | |
| dc.identifier | http://arxiv.org/abs/0806.1494 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212745 | |
| dc.subject | Combinatorics | |
| dc.subject | Discrete Mathematics | |
| dc.subject | G.2.1 ; F.2.2 | |
| dc.title | Posets and Permutations in the Duplication-Loss Model: Minimal Permutations with d Descents | |
| dc.type | text |