Circular Super patterns and Zigzag constructions

Resumen Técnico: Patrones Supercirculares y Construcciones en Zigzag

Título original: Circular Super patterns and Zigzag constructions
Autores: M. Hariprasad y Raisa Dsouza (Chanakya University, India)

1. El Problema

El estudio de los superpatrones es un problema fundamental en la teoría de permutaciones. Un $k$-superpatrón es una permutación que contiene todas las permutaciones posibles de longitud $k$ como subsecuencias orden-isomórficas. Históricamente, la investigación se ha centrado en encontrar la longitud mínima $L(k)$ de tales permutaciones.

Este artículo introduce una extensión de este concepto: el $k$-superpatrón circular. En este marco, las permutaciones se consideran dispuestas en un ciclo, lo que significa que los patrones se consideran equivalentes bajo rotación cíclica. El objetivo es determinar la longitud mínima $L_{circ}(k)$ de una permutación que contenga todas las clases de equivalencia cíclica de permutaciones de longitud $k$.

2. Metodología

Los autores emplean tres enfoques metodológicos principales:

• Construcción Recursiva: Utilizan superpatrones lineales conocidos para construir superpatrones circulares.
• Adaptación del Marco de Zigzag: Se basan en el trabajo de Engen y Vatter (2021), quienes utilizaron "palabras zigzag" para construir superpatrones lineales. Los autores adaptan y simplifican la función de puntuación (score function) de Engen y Vatter para el entorno circular.
• Análisis de Paridad: Introducen un análisis basado en la paridad de los elementos y las transiciones entre ellos para estudiar cómo se insertan los patrones en las secuencias zigzag.

3. Contribuciones Clave y Resultados

A. Límite Superior General:
Demuestran que un $k$-superpatrón circular puede construirse a partir de un $(k-1)$-superpatrón lineal $\pi$ de longitud $L$. Al añadir un elemento máximo al inicio ($\gamma = (L+1, \pi_1, \dots, \pi_L)$), se obtiene un superpatrón circular. Esto establece el límite:
$$L_{circ}(k) \leq L(k-1) + 1$$

B. Función de Puntuación Circular:
Los autores definen una función de costo local circular ($C_{xy}$) que cuantifica cuántas "carreras" (runs) adicionales de la secuencia zigzag se requieren para posicionar un número $y$ después de $x$ en un ciclo.

• Introducen la identidad de elevación circular (Circular lift identity): $S_c(\sigma) + S_c(\sigma^+) = 0$.
• Demuestran que para $k$ impar, la puntuación circular $S_c(\sigma)$ nunca es cero, lo cual es crucial para garantizar la existencia de un patrón o su versión desplazada ($\sigma^+$) dentro de la estructura zigzag.

C. Construcción para $k$ Impar:
Proponen una construcción específica para $k$ impar utilizando una modificación de la palabra zigzag $zz(k-1, k-1)$. Al reemplazar los últimos elementos por $(k, k-1)$ y aplicar el método de "romper empates" (breaking ties), generan una permutación $\gamma_k$ que actúa como superpatrón circular. Esta construcción ha sido verificada computacionalmente para valores pequeños de $k$.

D. Caso para $k$ Par:
Para $k$ par, demuestran un resultado ligeramente más débil pero relevante: cualquier patrón de longitud $k$ ocurre como una subsecuencia circular orden-isomórfica en $zz(k-1, k+1)$.

4. Significancia

Este trabajo es significativo porque:

1. Expande el dominio de la teoría de patrones: Pasa de la estructura lineal tradicional a una estructura topológica circular, lo cual es más natural para ciertos problemas de combinatoria y computación.
2. Optimización de estructuras: Proporciona herramientas matemáticas (como la función de puntuación circular) para entender la densidad de patrones en secuencias altamente estructuradas como las de zigzag.
3. Base para futuras investigaciones: Abre la puerta al estudio de la complejidad asintótica de $L_{circ}(k)$ y su aplicación en redes cíclicas o secuencias biológicas.

Clasificación AMS: 05A05, 05A15, 68R05 (Combinatoria y Algoritmos).