Conjecture on Maximal Sublattices of Finite Semidistributive Lattices and Beyond

Titolo: Congettura sui Sottoreticoli Massimali di Reti Semidistributive Finite e Oltre
Autori: K. Adaricheva, A. Mata, S. Silberger e A. Zamojska-Dzienio

1. Enunciato del Problema e Motivazione

Il lavoro indaga le proprietà strutturali dei complementi dei sottoreticoli massimali all'interno di reti finite. Un sottoreticolo proprio $S$ di una rete $L$ è massimale se l'aggiunta di qualsiasi elemento $x \in L \setminus S$ genera l'intera rete $L$. Il problema centrale consiste nel caratterizzare l'insieme $C = L \setminus S$ (il complemento).

Lavori precedenti hanno stabilito che, per le reti distributive finite, il complemento di un sottoreticolo massimale è sempre un singolo intervallo $[a, b]$, dove $a$ è un unico elemento irriducibile per unione e $b$ è un unico elemento irriducibile per intersezione. Per le reti limitate (immagini omomorfe limitate di reti libere), è stato inoltre dimostrato che tali complementi sono intervalli.

Gli autori si concentrano sull'estensione di questi risultati a classi più ampie:

1. Reti Semidistributive (SD): L'intersezione delle reti semidistributive per unione ($SD^\vee$) e semidistributive per intersezione ($SD^\wedge$).
2. Geometrie Convesse (CG): Una sottoclasse delle reti $SD^\vee$ che sono semimodulari inferiormente.

Il lavoro affronta la Domanda 1: Per quali classi di reti i complementi dei sottoreticoli massimali sono intervalli?

Gli autori propongono tre ipotesi:

• Ipotesi 1: I complementi dei sottoreticoli massimali di reti SD finite sono intervalli.
• Ipotesi 2: Per le reti $SD^\vee$ (in particolare le CG), i complementi sono unioni di intervalli che condividono un elemento minimo comune. (Dualmente, per le $SD^\wedge$, condividono un elemento massimo comune).
• Ipotesi 3: In qualsiasi rete finita, il complemento di un sottoreticolo massimale è convesso per ordine.

2. Metodologia

Il lavoro impiega una combinazione di teoria strutturale delle reti e analisi algoritmica:

• Analisi Strutturale: Gli autori utilizzano le proprietà degli elementi irriducibili per unione ($Ji(L)$) e irriducibili per intersezione ($Mi(L)$), le rappresentazioni canoniche per unione/intersezione e le applicazioni $\kappa$ e $\kappa_\sigma$ specifiche delle reti semidistributive. Analizzano i "joinands canonici stretti" e i "meetands canonici stretti" rispetto all'insieme del complemento.
• Decomposizione per Casi: Lo studio decompone il problema per classe di rete:
  • Reti finite generali (Osservazioni sulla convessità per ordine e sull'irriducibilità).
  • Reti $SD^\vee$ e $SD^\wedge$ (concentrandosi sull'esistenza di elementi massimi/minimi nel complemento).
  • Reti Semidistributive (SD) (combinando proprietà duali).
  • Geometrie Convess con dimensione convessa ($cdim$) = 2.
• Costruzione Algoritmica: Per il caso specifico delle CG con $cdim = 2$, gli autori derivano una procedura costruttiva per identificare tutti i possibili complementi basati sulle catene generatrici. Implementano ciò come un algoritmo e ne analizzano la complessità computazionale.
• Controesempi ed Esempi: Il lavoro utilizza costruzioni specifiche di reti (ad esempio, il raddoppio di Day, gli esempi di Jonsson-Nation) e figure per dimostrare dove le proprietà generali degli intervalli falliscono e dove le ipotesi proposte valgono.

3. Contributi e Risultati Chiave

Osservazioni Generali (Sezione 3)

• Convessità per Ordine: Gli autori forniscono prove a sostegno dell'Ipotesi 3. Dimostrano che se un complemento $C$ possiede un unico elemento minimo, esso è convesso per ordine. Mostrano inoltre che se $C$ possiede un unico elemento massimo, esso è convesso per ordine.
• Irriducibilità: Stabiliscono che gli elementi minimi di un complemento devono essere irriducibili per unione e gli elementi massimi devono essere irriducibili per intersezione. Nessun elemento in un complemento con $|C| \ge 2$ può essere doppiamente irriducibile.

Reti Semidistributive (Sezioni 4 e 5)

• Risultati su $SD^\vee$ e $SD^\wedge$: Gli autori dimostrano che se il complemento di un sottoreticolo massimale in una rete $SD^\vee$ possiede un elemento massimo, esso è un intervallo (Teorema 4.5). Dualmente, se il complemento di una rete $SD^\wedge$ possiede un elemento minimo, esso è un intervallo.
• Reti SD: Il Teorema 5.5 afferma che se un complemento $C$ in una rete SD contiene un elemento confrontabile con ogni altro elemento in $C$, allora $C$ è un intervallo.
• Limiti: Il lavoro dimostra, tramite esempi (Figura 2), che per reti $SD^\vee$ generali (in particolare CG con $cdim = n$), il complemento può essere una unione di $n$ intervalli che condividono un elemento minimo comune, smentendo l'idea che siano sempre singoli intervalli. Ciò supporta l'Ipotesi 2 piuttosto che l'Ipotesi 1 per la classe più ampia $SD^\vee$.

Geometrie Convess con $cdim = 2$ (Sezione 6)

Questo è il principale risultato tecnico del lavoro. Gli autori forniscono una caratterizzazione completa dei complementi per le CG generate da due catene.

• Teorema 6.1: Il complemento di un sottoreticolo massimale in una CG con $cdim = 2$ è precisamente una delle tre forme seguenti:
  1. Un singolo intervallo $[(j), C_i(j)]$ dove l'elemento minimo $(j)$ non si trova sull'altra catena.
  2. Un singolo intervallo $[(j), C_i(j)]$ dove $(j)$ si trova sull'altra catena, ma si applicano condizioni di ordinamento specifiche.
  3. Una unione di due intervalli $[(j), C_1(j)] \cup [(j), C_2(j)]$ che condividono l'elemento minimo $(j)$, dove $(j)$ non si trova su nessuna delle due catene.
• Conferma delle Ipotesi: Per $cdim = 2$, le Ipotesi 2, 3 e 4 (riguardo all'esistenza di un sottocopertura nel sottoreticolo per ogni elemento nel complemento) sono confermate.
• Algoritmo 6.8: Gli autori presentano un algoritmo per trovare tutti tali complementi date le catene generatrici.
  • Complessità: L'algoritmo esegue in tempo $O(n)$, dove $n$ è la dimensione dell'insieme di base.
  • Prestazioni: I test empirici mostrano che l'algoritmo è significativamente più veloce dei metodi nativi di SageMath per $n \ge 20$, con i metodi nativi che non riescono a completare per $n \ge 30$ entro tempi ragionevoli.

4. Significato e Affermazioni

Il lavoro afferma di avviare uno studio sistematico della "congettura dell'intervallo" per le reti semidistributive. Il suo significato risiede in:

1. Raffinamento dell'Ambito: Chiarisce che, mentre la proprietà "il complemento è un intervallo" vale per le reti limitate e distributive, essa si generalizza alle reti SD solo sotto condizioni specifiche (ad esempio, l'esistenza di un elemento confrontabile nel complemento).
2. Caratterizzazione di $SD^\vee$: Stabilisce che per le reti $SD^\vee$ la struttura è più complessa (unioni di intervalli), ma per la specifica sottoclasse delle Geometrie Convess con $cdim=2$, è possibile una classificazione completa e calcolabile.
3. Efficienza Computazionale: Fornendo un algoritmo $O(n)$ per $cdim=2$, il lavoro offre uno strumento pratico per esplorare queste strutture, in netto contrasto con la complessità esponenziale dell'enumerazione generale dei sottoreticoli massimali.

Gli autori notano modestamente che, sebbene abbiano confermato le ipotesi per $cdim=2$, l'estensione di questi risultati a $cdim=3$ introduce una maggiore variabilità e rimane un'area aperta per lavori futuri. Menzionano inoltre risultati preliminari riguardanti il sottoreticolo di Frattini nelle CG, notando che le reti booleane su 2 elementi non possono essere il sottoreticolo di Frattini di una CG con $cdim=2$.