Códigos cuasi perfectos en el producto cartesiano de algunos grafos

Información Básica

• ID del Artículo: 2510.13613
• Título: Códigos cuasi perfectos en el producto cartesiano de algunos grafos
• Autores: S. A. Mane, N. V. Shinde
• Clasificación: math.CO (Matemática Combinatoria)
• Fecha de Publicación: 15 de octubre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2510.13613

Resumen

Una cuestión importante en la investigación de códigos cuasi perfectos es si es posible construir tales códigos para todas las longitudes n posibles. Este artículo aborda esta cuestión para valores específicos de n. En primer lugar, se estudia la existencia de códigos cuasi perfectos en el producto cartesiano de un grafo G que admite un código perfecto con caminos (o ciclos). En segundo lugar, se exploran códigos cuasi perfectos en productos cartesianos de dos o tres ciclos $C_m\square C_n$ y $C_m\square C_n\square C_l$, así como en productos cartesianos de dos o tres caminos $P_m\square P_n$ y $P_m\square P_n\square P_l$.

Antecedentes de Investigación y Motivación

1. Problema a Resolver: Esta investigación tiene como objetivo resolver el problema de existencia en la construcción de códigos cuasi perfectos, particularmente métodos sistemáticos para construir códigos cuasi perfectos en productos cartesianos de grafos.
2. Importancia del Problema:
   • Los códigos perfectos desempeñan un papel central en la teoría de códigos correctores de errores, pero son relativamente escasos
   • La conjetura de Golomb-Welch afirma que no existen códigos Lee e-correctores de errores perfectos de longitud n≥3 con e>1
   • Los códigos cuasi perfectos, como aproximaciones de códigos perfectos, poseen valor teórico y aplicado significativo
3. Limitaciones de Métodos Existentes:
   • Las condiciones de existencia para códigos cuasi perfectos siguen siendo bastante restrictivas
   • Se conocen muy pocos códigos cuasi perfectos con radio de cobertura mayor que 3
   • Faltan métodos de construcción sistemáticos
4. Motivación de la Investigación: Desarrollar técnicas para construir códigos cuasi perfectos en productos cartesianos de G con grafos específicos, basándose en códigos perfectos en el grafo G.

Contribuciones Principales

1. Se propone un método sistemático para construir códigos cuasi perfectos basado en códigos perfectos: Si el grafo G admite un código e-corrector de errores perfecto, entonces se pueden construir códigos e-correctores de errores cuasi perfectos en G□Pn o G□Cn
2. Se construyen diversos códigos cuasi perfectos concretos:
   • Códigos 2-correctores de errores cuasi perfectos en Pm□Pn□P6k-2 y Cm□Cn□C6k
   • Códigos cuasi perfectos en P4□P4□P4 basados en códigos perfectos en P2□P2□P2
3. Se extienden resultados conocidos: Construcción de códigos cuasi perfectos en Cn□Cn□Cl (3≤n≤19), utilizando códigos cuasi perfectos conocidos en Cn□Cn
4. Se proporciona un marco teórico completo: Análisis sistemático de métodos de construcción de códigos cuasi perfectos en productos cartesianos de caminos y ciclos

Explicación Detallada de Métodos

Definición de la Tarea

Dado un grafo G, construir códigos cuasi perfectos en su producto cartesiano con un camino Pn o un ciclo Cn, es decir, en G□Pn y G□Cn. Un código D es t-cuasi perfecto si y solo si es t-corrector de errores y tiene radio de cobertura t+1.

Métodos de Construcción Principales

1. Teorema de Construcción Fundamental (Teorema 3.1)

Para un código e-corrector de errores perfecto D en el grafo G:

• Cuando e=1: Se pueden construir códigos 1-correctores de errores cuasi perfectos en G□P3k y G□C3k
• Cuando e≥2: Se pueden construir códigos e-correctores de errores cuasi perfectos en G□P3 y G□C3

Método de Construcción:

D' = D ⊕ {1}

donde ⊕ denota el producto directo de conjuntos.

2. Construcción de Extensión Tridimensional (Teorema 3.2)

Para un código 2-corrector de errores perfecto D1 en Pm□Pn, construir un código 2-corrector de errores cuasi perfecto en Pm□Pn□P6k-2:

Pasos:

1. Definir D2 = (0,3) + D1 (código trasladado)
2. Construir D = (D1⊕{0}) ∪ (D2⊕{3})
3. Extender a dimensiones mayores: C = ⋃(i=0 a k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. Construcción de Producto de Ciclos

Teorema 3.6: Construir un código 1-corrector de errores cuasi perfecto en C3□C6□C4k

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 a k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

Puntos de Innovación Técnica

1. Estrategia de Construcción Estratificada: Descomponer grafos de alta dimensión en capas de baja dimensión, aplicando códigos perfectos conocidos en cada capa
2. Técnica de Traslación: Garantizar que las palabras de código en diferentes capas mantengan la distancia mínima mediante operaciones de traslación apropiadas
3. Extensión Periódica: Realizar construcciones de tamaño arbitrario mediante repetición periódica de bloques de construcción fundamental

Configuración Experimental

Métodos de Verificación

El artículo verifica principalmente la corrección de las construcciones mediante pruebas teóricas, complementadas con búsqueda computacional para casos específicos:

1. Verificación Teórica: Demostrar la distancia mínima y el radio de cobertura del código construido
2. Verificación Computacional: Para casos complejos (como ciertos parámetros en el Teorema 4.4), utilizar búsqueda computacional para verificación

Indicadores de Evaluación

• Distancia Mínima: Distancia mínima entre cualesquiera dos palabras de código
• Radio de Cobertura: Distancia máxima desde cualquier vértice a la palabra de código más cercana
• Cuasi Perfección: Verificar que radio de cobertura = capacidad correctora + 1

Resultados Experimentales

Resultados Principales

1. Resultados del Teorema 3.1:
   • Cuando e=1, construcción exitosa de códigos 1-correctores de errores cuasi perfectos en G□P3k y G□C3k
   • Cuando e≥2, construcción exitosa de códigos e-correctores de errores cuasi perfectos en G□P3 y G□C3
2. Resultados de Construcción Tridimensional:
   • Construcción de códigos 2-correctores de errores cuasi perfectos en Pm□Pn□P6k-2 (Teorema 3.2)
   • Construcción de códigos 2-correctores de errores cuasi perfectos en Cm□Cn□C6k (Corolario 3.3)
3. Instancias Concretas:
   • Código 1-corrector de errores perfecto en C6□C6□C2 (Teorema 4.2)
   • Código 1-corrector de errores cuasi perfecto en C3□C6□C4k (Teorema 3.6)

Tabla Resumen de Construcciones

Análisis de Casos

El artículo proporciona múltiples instancias de construcción concretas, tales como:

• Figura 1 muestra un código 1-corrector de errores cuasi perfecto en P4□P4□P4
• Figuras 2-6 muestran construcciones de códigos cuasi perfectos en varios productos de ciclos

Trabajos Relacionados

1. Teoría de Códigos Perfectos: Basada en la teoría de conjuntos de control perfecto de Livingston y Stout
2. Códigos bajo Métrica Lee: Línea de investigación impulsada por la conjetura de Golomb-Welch
3. Construcción de Códigos Cuasi Perfectos: Trabajo de construcción de AlBdaiwi y otros bajo métrica Lee
4. Códigos en Teoría de Grafos: Teoría de códigos correctores de errores basada en distancia de grafos

Conclusiones y Discusión

Conclusiones Principales

1. Se establece exitosamente un método sistemático para construir códigos cuasi perfectos a partir de códigos perfectos
2. Se proporcionan construcciones explícitas de códigos cuasi perfectos para productos cartesianos de diversos grafos
3. Se extienden los resultados conocidos sobre existencia de códigos cuasi perfectos

Limitaciones

1. Los métodos de construcción dependen de la existencia de códigos perfectos en grafos base
2. La construcción para ciertos rangos de parámetros aún requiere verificación computacional
3. La aplicabilidad del método de construcción es limitada para productos cartesianos de grafos generales

Direcciones Futuras

1. Determinar para cuáles enteros n y grafos G2 se pueden construir códigos cuasi perfectos en el producto cartesiano de G1 con n copias de G2
2. Identificar todos los valores de parámetros (m,n,l) tales que Cm□Cn□Cl admita códigos cuasi perfectos
3. Generalizar a clases de grafos más generales y espacios métricos

Evaluación Profunda

Fortalezas

1. Rigor Teórico: Todas las construcciones poseen demostraciones matemáticas completas
2. Método Sistemático: Proporciona un marco de construcción unificado
3. Valor Práctico: Los métodos de construcción son aplicables a múltiples casos concretos
4. Ayuda Visual: Las ilustraciones abundantes facilitan la comprensión del proceso de construcción

Deficiencias

1. Limitaciones de Aplicabilidad: El método se aplica principalmente a productos cartesianos de caminos y ciclos
2. Complejidad Computacional: La verificación de algunas construcciones requiere cálculo extenso
3. Optimalidad: No se discute la optimalidad de los códigos construidos

Impacto

1. Contribución Teórica: Proporciona nuevas técnicas de construcción para la teoría de códigos cuasi perfectos
2. Perspectivas de Aplicación: Aplicaciones potenciales en codificación de redes y almacenamiento distribuido
3. Escalabilidad: El método de construcción proporciona base para investigación adicional

Escenarios de Aplicación

1. Escenarios que requieren despliegue de códigos correctores de errores en topologías de red regulares
2. Control de errores en redes de malla multidimensional y redes toroidales
3. Problemas de colocación de recursos tolerantes a fallos en sistemas distribuidos

Referencias Bibliográficas

El artículo cita 33 referencias relacionadas, incluyendo principalmente:

• Golomb & Welch (1970): Trabajo pionero en códigos perfectos bajo métrica Lee
• AlBdaiwi & Bose (2003): Códigos Lee de distancia cuasi perfecta
• Livingston & Stout (1990): Teoría de conjuntos de control perfecto
• Múltiples investigaciones recientes sobre construcción de códigos cuasi perfectos

Evaluación General: Este es un artículo de alta calidad en el campo interdisciplinario de matemática combinatoria y teoría de códigos, que proporciona métodos de construcción sistemáticos para códigos cuasi perfectos, con rigor teórico y valor práctico considerable, sentando una base sólida para el desarrollo futuro de este campo.