Ancho gemelo y permutaciones

Inspirados por un invariante de ancho en permutaciones definido por Guillemot y Marx, Bonnet, Kim, Thomassé y Watrigant introdujeron el ancho gemelo de los grafos, que es un parámetro que describe su complejidad estructural. Este invariante se ha extendido aún más a estructuras binarias, de varias maneras (básicamente equivalentes). Demostramos que una clase de estructuras relacionales binarias (es decir: grafos parcialmente dirigidos coloreados por bordes) tiene ancho gemelo acotado si y solo si es una transducción de primer orden de una clase de permutaciones apropiada. Como un subproducto, mostramos que cada clase con ancho gemelo acotado contiene como máximo 2^O(n) grafos de n vértices, no isomorfos entre sí.