Conjecture on Maximal Sublattices of Finite Semidistributive Lattices and Beyond

Título: Conjectura sobre Sub-reticulados Maximais de Reticulados Semidistributivos Finitos e Além
Autores: K. Adaricheva, A. Mata, S. Silberger e A. Zamojska-Dzienio

1. Formulação do Problema e Motivação

O artigo investiga as propriedades estruturais dos complementos de sub-reticulados maximais dentro de reticulados finitos. Um sub-reticulado próprio $S$ de um reticulado $L$ é maximal se a adição de qualquer elemento $x \in L \setminus S$ gerar todo o reticulado $L$. O problema central é caracterizar o conjunto $C = L \setminus S$ (o complemento).

Trabalhos anteriores estabeleceram que, para reticulados distributivos finitos, o complemento de um sub-reticulado maximal é sempre um único intervalo $[a, b]$, onde $a$ é um elemento único irredutível por junção e $b$ é um elemento único irredutível por encontro. Para reticulados limitados (imagens homomórficas limitadas de reticulados livres), também foi demonstrado que esses complementos são intervalos.

Os autores concentram-se em estender esses resultados a classes mais amplas:

1. Reticulados Semidistributivos (SD): A interseção de reticulados semidistributivos por junção ($SD^\vee$) e semidistributivos por encontro ($SD^\wedge$).
2. Geometrias Convexas (GCs): Uma subclasse de reticulados $SD^\vee$ que são semimodulares inferiores.

O artigo aborda a Questão 1: Para quais classes de reticulados os complementos de sub-reticulados maximais são intervalos?

Os autores propõem três hipóteses:

• Hipótese 1: Os complementos de sub-reticulados maximais de reticulados SD finitos são intervalos.
• Hipótese 2: Para reticulados $SD^\vee$ (especificamente GCs), os complementos são uniões de intervalos que compartilham um elemento mínimo comum. (Dualmente, para $SD^\wedge$, eles compartilham um elemento máximo comum).
• Hipótese 3: Em qualquer reticulado finito, o complemento de um sub-reticulado maximal é convexo em relação à ordem.

2. Metodologia

O artigo emprega uma combinação de teoria estrutural de reticulados e análise algorítmica:

• Análise Estrutural: Os autores utilizam propriedades de elementos irredutíveis por junção ($Ji(L)$) e irredutíveis por encontro ($Mi(L)$), representações canônicas de junção/encontro e as aplicações $\kappa$ e $\kappa_\sigma$ específicas de reticulados semidistributivos. Eles analisam os "componentes canônicos estritos de junção" e "componentes canônicos estritos de encontro" em relação ao conjunto complemento.
• Decomposição de Casos: O estudo decompõe o problema por classe de reticulado:
  • Reticulados finitos gerais (Observações sobre convexidade em relação à ordem e irredutibilidade).
  • Reticulados $SD^\vee$ e $SD^\wedge$ (focando na existência de elementos máximo/mínimo no complemento).
  • Reticulados Semidistributivos (SD) (combinando propriedades duais).
  • Geometrias Convexas com dimensão convexa ($cdim$) = 2.
• Construção Algorítmica: Para o caso específico de GCs com $cdim = 2$, os autores derivam um procedimento construtivo para identificar todos os complementos possíveis com base nas cadeias geradoras. Eles implementam isso como um algoritmo e analisam sua complexidade computacional.
• Contraexemplos e Exemplos: O artigo utiliza construções específicas de reticulados (por exemplo, duplicação de Day, exemplos de Jonsson-Nation) e figuras para demonstrar onde as propriedades gerais de intervalo falham e onde as hipóteses propostas se sustentam.

3. Contribuições e Resultados Principais

Observações Gerais (Seção 3)

• Convexidade em Relação à Ordem: Os autores fornecem evidências para a Hipótese 3. Eles provam que, se um complemento $C$ possui um elemento mínimo único, ele é convexo em relação à ordem. Eles também mostram que, se $C$ possui um elemento máximo único, ele é convexo em relação à ordem.
• Irredutibilidade: Eles estabelecem que os elementos mínimos de um complemento devem ser irredutíveis por junção e os elementos máximos devem ser irredutíveis por encontro. Nenhum elemento em um complemento com $|C| \ge 2$ pode ser duplamente irredutível.

Reticulados Semidistributivos (Seções 4 e 5)

• Resultados para $SD^\vee$ e $SD^\wedge$: Os autores provam que, se o complemento de um sub-reticulado maximal em um reticulado $SD^\vee$ possui um elemento máximo, ele é um intervalo (Teorema 4.5). Dualmente, se o complemento de um reticulado $SD^\wedge$ possui um elemento mínimo, ele é um intervalo.
• Reticulados SD: O Teorema 5.5 afirma que, se um complemento $C$ em um reticulado SD contém um elemento comparável a todo outro elemento em $C$, então $C$ é um intervalo.
• Limitações: O artigo demonstra, por meio de exemplos (Figura 2), que para reticulados $SD^\vee$ gerais (especificamente GCs com $cdim = n$), o complemento pode ser uma união de $n$ intervalos que compartilham um elemento mínimo comum, refutando a ideia de que são sempre intervalos únicos. Isso apoia a Hipótese 2 em vez da Hipótese 1 para a classe mais ampla $SD^\vee$.

Geometrias Convexas com $cdim = 2$ (Seção 6)

Este é o principal feito técnico do artigo. Os autores fornecem uma caracterização completa dos complementos para GCs geradas por duas cadeias.

• Teorema 6.1: O complemento de um sub-reticulado maximal em uma GC com $cdim = 2$ é precisamente uma das três formas:
  1. Um único intervalo $[(j), C_i(j)]$ onde o elemento mínimo $(j)$ não está na outra cadeia.
  2. Um único intervalo $[(j), C_i(j)]$ onde $(j)$ está na outra cadeia, mas condições específicas de ordenação se aplicam.
  3. Uma união de dois intervalos $[(j), C_1(j)] \cup [(j), C_2(j)]$ compartilhando o elemento mínimo $(j)$, onde $(j)$ não está em nenhuma das cadeias.
• Confirmação das Hipóteses: Para $cdim = 2$, as Hipóteses 2, 3 e 4 (relativas à existência de uma subcobertura no sub-reticulado para cada elemento no complemento) são confirmadas.
• Algoritmo 6.8: Os autores apresentam um algoritmo para encontrar todos esses complementos dadas as cadeias geradoras.
  • Complexidade: O algoritmo executa em tempo $O(n)$, onde $n$ é o tamanho do conjunto base.
  • Desempenho: Testes empíricos mostram que o algoritmo é significativamente mais rápido que os métodos nativos do SageMath para $n \ge 20$, com os métodos nativos falhando em completar para $n \ge 30$ dentro de prazos razoáveis.

4. Significado e Afirmações

O artigo afirma iniciar um estudo sistemático da "conjectura do intervalo" para reticulados semidistributivos. Seu significado reside em:

1. Refinar o Escopo: Ele esclarece que, embora a propriedade "o complemento é um intervalo" valha para reticulados limitados e distributivos, ela se generaliza para reticulados SD apenas sob condições específicas (por exemplo, existência de um elemento comparável no complemento).
2. Caracterizar $SD^\vee$: Ele estabelece que, para reticulados $SD^\vee$, a estrutura é mais complexa (uniões de intervalos), mas para a subclasse específica de Geometrias Convexas com $cdim=2$, uma classificação completa e computável é possível.
3. Eficiência Computacional: Ao fornecer um algoritmo $O(n)$ para $cdim=2$, o artigo oferece uma ferramenta prática para explorar essas estruturas, contrastando fortemente com a complexidade exponencial da enumeração geral de sub-reticulados maximais.

Os autores observam modestamente que, embora tenham confirmado as hipóteses para $cdim=2$, estender esses resultados para $cdim=3$ introduz maior variabilidade e permanece uma área aberta para trabalho futuro. Eles também mencionam resultados preliminares relativos ao sub-reticulado de Frattini em GCs, observando que reticulados booleanos sobre 2 elementos não podem ser o sub-reticulado de Frattini de uma GC com $cdim=2$.