Conjecture on Maximal Sublattices of Finite Semidistributive Lattices and Beyond

Título: Conjetura sobre Subretículos Maximales de Retículos Semidistributivos Finitos y Más Allá
Autores: K. Adaricheva, A. Mata, S. Silberger y A. Zamojska-Dzienio

1. Planteamiento del Problema y Motivación

El artículo investiga las propiedades estructurales de los complementos de subretículos maximales dentro de retículos finitos. Un subretículo propio $S$ de un retículo $L$ es maximal si añadir cualquier elemento $x \in L \setminus S$ genera todo el retículo $L$. El problema central es caracterizar el conjunto $C = L \setminus S$ (el complemento).

Trabajos anteriores establecieron que, para retículos distributivos finitos, el complemento de un subretículo maximal es siempre un único intervalo $[a, b]$, donde $a$ es un elemento único irreducible por unión y $b$ es un elemento único irreducible por intersección. Para retículos acotados (imágenes homomorfas acotadas de retículos libres), también se demostró que estos complementos son intervalos.

Los autores se centran en extender estos resultados a clases más amplias:

1. Retículos Semidistributivos (SD): La intersección de retículos semidistributivos por unión ($SD^\vee$) y semidistributivos por intersección ($SD^\wedge$).
2. Geometrías Convexas (GCs): Una subclase de retículos $SD^\vee$ que son semimodulares inferiores.

El artículo aborda la Pregunta 1: ¿Para qué clases de retículos los complementos de subretículos maximales son intervalos?

Los autores proponen tres hipótesis:

• Hipótesis 1: Los complementos de subretículos maximales de retículos SD finitos son intervalos.
• Hipótesis 2: Para retículos $SD^\vee$ (específicamente GCs), los complementos son uniones de intervalos que comparten un elemento mínimo común. (Dualmente, para $SD^\wedge$, comparten un elemento máximo común).
• Hipótesis 3: En cualquier retículo finito, el complemento de un subretículo maximal es convexo por orden.

2. Metodología

El artículo emplea una combinación de teoría estructural de retículos y análisis algorítmico:

• Análisis Estructural: Los autores utilizan propiedades de elementos irreducibles por unión ($Ji(L)$) e irreducibles por intersección ($Mi(L)$), representaciones canónicas de unión/intersección y las aplicaciones $\kappa$ y $\kappa_\sigma$ específicas de retículos semidistributivos. Analizan los "sumandos canónicos estrictos" y "términos canónicos estrictos de intersección" en relación con el conjunto complemento.
• Descomposición por Casos: El estudio descompone el problema por clase de retículo:
  • Retículos finitos generales (Observaciones sobre convexidad por orden e irreducibilidad).
  • Retículos $SD^\vee$ y $SD^\wedge$ (centrándose en la existencia de elementos máximo/mínimo en el complemento).
  • Retículos Semidistributivos (SD) (combinando propiedades duales).
  • Geometrías Convexas con dimensión convexa ($cdim$) = 2.
• Construcción Algorítmica: Para el caso específico de GCs con $cdim = 2$, los autores derivan un procedimiento constructivo para identificar todos los complementos posibles basándose en las cadenas generadoras. Implementan esto como un algoritmo y analizan su complejidad computacional.
• Contraejemplos y Ejemplos: El artículo utiliza construcciones específicas de retículos (por ejemplo, el doblez de Day, ejemplos de Jonsson-Nation) y figuras para demostrar dónde fallan las propiedades generales de intervalo y dónde se cumplen las hipótesis propuestas.

3. Contribuciones y Resultados Clave

Observaciones Generales (Sección 3)

• Convexidad por Orden: Los autores proporcionan evidencia para la Hipótesis 3. Demuestran que si un complemento $C$ tiene un elemento mínimo único, es convexo por orden. También muestran que si $C$ tiene un elemento máximo único, es convexo por orden.
• Irreducibilidad: Establecen que los elementos mínimos de un complemento deben ser irreducibles por unión y los elementos máximos deben ser irreducibles por intersección. Ningún elemento en un complemento con $|C| \ge 2$ puede ser doblemente irreducible.

Retículos Semidistributivos (Secciones 4 y 5)

• Resultados $SD^\vee$ y $SD^\wedge$: Los autores demuestran que si el complemento de un subretículo maximal en un retículo $SD^\vee$ tiene un elemento máximo, es un intervalo (Teorema 4.5). Dualmente, si el complemento de un retículo $SD^\wedge$ tiene un elemento mínimo, es un intervalo.
• Retículos SD: El Teorema 5.5 establece que si un complemento $C$ en un retículo SD contiene un elemento comparable con todos los demás elementos en $C$, entonces $C$ es un intervalo.
• Limitaciones: El artículo demuestra mediante ejemplos (Figura 2) que para retículos $SD^\vee$ generales (específicamente GCs con $cdim = n$), el complemento puede ser una unión de $n$ intervalos que comparten un elemento mínimo común, refutando la idea de que siempre son intervalos únicos. Esto apoya la Hipótesis 2 en lugar de la Hipótesis 1 para la clase más amplia de $SD^\vee$.

Geometrías Convexas con $cdim = 2$ (Sección 6)

Este es el logro técnico principal del artículo. Los autores proporcionan una caracterización completa de los complementos para GCs generadas por dos cadenas.

• Teorema 6.1: El complemento de un subretículo maximal en una GC con $cdim = 2$ es precisamente una de tres formas:
  1. Un único intervalo $[(j), C_i(j)]$ donde el elemento mínimo $(j)$ no está en la otra cadena.
  2. Un único intervalo $[(j), C_i(j)]$ donde $(j)$ está en la otra cadena, pero se aplican condiciones de ordenamiento específicas.
  3. Una unión de dos intervalos $[(j), C_1(j)] \cup [(j), C_2(j)]$ que comparten el elemento mínimo $(j)$, donde $(j)$ no está en ninguna de las cadenas.
• Confirmación de Hipótesis: Para $cdim = 2$, se confirman las Hipótesis 2, 3 y 4 (respecto a la existencia de un subrecubrimiento en el subretículo para cada elemento en el complemento).
• Algoritmo 6.8: Los autores presentan un algoritmo para encontrar todos esos complementos dadas las cadenas generadoras.
  • Complejidad: El algoritmo se ejecuta en tiempo $O(n)$, donde $n$ es el tamaño del conjunto base.
  • Rendimiento: Las pruebas empíricas muestran que el algoritmo es significativamente más rápido que los métodos nativos de SageMath para $n \ge 20$, con los métodos nativos fallando en completarse para $n \ge 30$ dentro de plazos razonables.

4. Significado y Afirmaciones

El artículo afirma iniciar un estudio sistemático de la "conjetura del intervalo" para retículos semidistributivos. Su significado radica en:

1. Refinar el Alcance: Aclara que, aunque la propiedad "el complemento es un intervalo" se cumple para retículos acotados y distributivos, se generaliza a retículos SD solo bajo condiciones específicas (por ejemplo, existencia de un elemento comparable en el complemento).
2. Caracterizar $SD^\vee$: Establece que para retículos $SD^\vee$, la estructura es más compleja (uniones de intervalos), pero para la subclase específica de Geometrías Convexas con $cdim=2$, es posible una clasificación completa y computable.
3. Eficiencia Computacional: Al proporcionar un algoritmo $O(n)$ para $cdim=2$, el artículo ofrece una herramienta práctica para explorar estas estructuras, contrastando marcadamente con la complejidad exponencial de la enumeración general de subretículos maximales.

Los autores notan modestamente que, aunque han confirmado las hipótesis para $cdim=2$, extender estos resultados a $cdim=3$ introduce mayor variabilidad y sigue siendo un área abierta para trabajo futuro. También mencionan resultados preliminares respecto al subretículo de Frattini en GCs, señalando que los retículos booleanos sobre 2 elementos no pueden ser el subretículo de Frattini de una GC con $cdim=2$.