Tamaño máximo de la secuencia mínima de transposiciones cuyo producto es una permutación dada

Question

Considere la secuencia $S = 1,2,3,\ldots n$ de elementos, junto con una secuencia $T = t_1, t_2, \ldots, t_m$ de transposiciones. Cada transposición $t_i$ es una tupla $(a_i, b_i) \in [n]^2$ . Al aplicar una transposición $t_i$ a (una permutación de) $S$ intercambia los elementos en las posiciones $a_i$ y $b_i$ en la secuencia.

Aplicar todas las transposiciones $t_1, \ldots, t_m$ uno a uno en $S$ da como resultado una permutación final $R$ . Llamamos secuencia de transposición $T$ mínimo si no existe una subsecuencia adecuada $T'$ de $T$ cuya aplicación a $S$ daría como resultado la misma permutación $R$ . Mi pregunta es la siguiente: ¿cuál es la longitud máxima de una secuencia de transposición mínima, en términos de $n$ ? Está claro que este máximo es como máximo $n!$ si tenemos una secuencia con más de $n!$ transposiciones, entonces al aplicar las transposiciones en $T$ habrá 2 puntos en los que hayamos obtenido la misma permutación intermedia, y las transposiciones intermedias pueden eliminarse de la secuencia sin cambiar el resultado final. Lo que me pregunto es lo siguiente: ¿puede haber un límite superior polinómico en la longitud de una secuencia de transposición mínima? Si no es así, ¿qué aspecto tiene una secuencia de transposición mínima de longitud superpolinómica?

Edito: pido disculpas por mi exposición elemental de la pregunta; soy informático y estoy relativamente poco familiarizado con la literatura sobre teoría de grupos. Permítanme aclarar algunos puntos: mi uso de subsecuencia sigue el de Wikipedia . La secuencia de transposiciones $T$ contendrá, en general, transposiciones repetidas, de lo contrario un polinomio ( $n^2$ ) a la longitud de cualquier secuencia de este tipo sería trivial. No creo que mi pregunta pueda reformularse en términos de las propiedades del grafo de Cayley con un conjunto dado de transposiciones como generadores del grupo simétrico, porque me importa el pedir en que se aplican las transposiciones: al hacer una secuencia dada $T$ mínimo se le permite eliminar transposiciones de la secuencia, pero no reordenarlas.

Answer 1

Gracias por aclarar la pregunta. (Editaría más para indicar que subsecuencia es diferente de subcadena o subpalabra, por lo que no es necesariamente una porción contigua de la secuencia dada). La respuesta corta es que no lo sé, pero sospecho que la longitud no es supercuadrática por razones que aparecerán.

Escoge una secuencia T de transposiciones sobre las n letras, fija S en el conjunto de solteros de la permutación identidad e i en 1. Ahora calcula para cada permutación no coloreada (no verde) s en S la permutación s' = st_i. Si s' ya está en S, márquela en verde; si no, añada s' sin colorear a S. A continuación, incremente i. Compruebe si todos los miembros de S son verdes. Si es así, deténgase; si no, vuelva al bucle 'Ahora'. Edición 2016.04.07 : Gracias a Ilya Bogdanov, también debería calcular s'=st_i para los s verdes, y luego colorear esos s' instantáneamente al ponerlos en S; podría obtener un valor máximo más pequeño de i. Para abordar las preocupaciones del póster, este algoritmo debería ejecutarse para suficientes secuencias T para determinar el mayor valor de i dado n. También tiene mérito la sugerencia de Ilya de mirar el recuento de inversión usando secuencias de transposiciones adyacentes, ya que podría llevar a un límite inferior cuadrático en n de i máximo. Además, la sugerencia de Ilya de considerar el recuento de inversiones utilizando secuencias de transposiciones adyacentes tiene mérito, ya que podría conducir a un límite inferior cuadrático en n para el valor máximo de i. Sin embargo, se necesita más rigor para garantizar la minimalidad de una secuencia suficientemente larga de transposiciones adyacentes. Fin Edición 2016.04.07 .

Esto le dará un algoritmo para determinar la subcadena inicial más larga de T que sea mínima. Una vez que el algoritmo se detiene, i es demasiado grande. Como S tiene el potencial de ser 2^i en tamaño, y nos detenemos después de duplicar a lo sumo n! permutaciones en S, mi instinto dice i está limitado por cnlog n y definitivamente por n^2. Sin embargo, esto no es una prueba, ya que puede haber algunos holdouts. Nótese, sin embargo, que si el segmento inicial duplica un subconjunto de permutaciones, entonces cualquier secuencia que incluya ese segmento inicial como subcadena no es mínima.

Para valores pequeños de n, sólo debería ser ligeramente oneroso calcular la longitud máxima de dicha secuencia mínima. Predigo que 4n^2 es un límite superior débil en i para todo n. Si eliges subcadena en lugar de subsecuencia, creo que el crecimiento podría ser superpolinomial, y puedes escribir un algoritmo similar al anterior para probarlo.

Gerhard "Needs Practice In Formatting Pseudocode" Paseman, 2016.04.06.