Il polinomio caratteristico

1 Funzione di Moebius

Sia P un IPO. Si definisce la funzione
µ : P x P Z tale che

{ µ (x,x) = 1
µ [x,y] = - µ (x,z)
x<=z<y

Si dice funzione di Moebius dell'IPO P (dotato di 0) la funzione

µ : P Z tale che µ (x) = µ [0,x]
La funzione di Moebius è definibile anche come:

{ µ (0) = 1
µ (x) = - µ (z)
z<x

Dato un elemento x dell'IPO P, si dice Filtro o ideale ascendente di P l'insieme degli z maggiori o uguali a x

Dato un elemento x dell'IPO P, si dice Ideale d'ordine o insieme discendente di P l'insieme degli z minori o uguali a x

Un IPO ha la Chain-Condition quando i suoi sottoinsiemi totalmente ordinati che sono massimali hanno lo stesso numero di elementi. Per sottoinsieme massimale si intende un sottoinsieme al quale non può essere aggiunto un elemento senza perdere la totalità dell'ordine.

Sia P un IPO per il quale valga la Chain-Condition. Si definisce Rango la funzione r: P N tale che: r(x)= (ordine di una catena massimale di [0,x]) - 1

Sia P un IPO per il quale valga la Chain-Condition. Si dice altezza di P il rango dell'elemento massimo.

Esempio

Consideriamo l'algebra di Boole di 3 elementi

Lemma 1

Sia P un IPO dotato di zero, unità e funzione rango.
Sia y un elemento di P tale che cover{y} = (elementi coperti da y) = {a}, allora
{ -1 , a = 0p
µ(y) =
0 , altrimenti

Dimostrazione:

µ (y) = - µ (z)
z<y

= - ( µ (a) + µ (z))
az<y

= - µ (a) - µ (z)
z<a
a = 0p : µ (y) = - µ (a) = - µ (0) = - 1
a 0p : µ (y) = - µ (a) + µ (a) = 0

Lemma 2

Sia P un IPO dotato di zero, unità e funzione rango.
Sia y un elemento di P tale che cover{y} = (elementi coperti da y) = { a, b }, dove a e b sono tali che r(a) = r(b) e per essi sia definita la massima delimitazione inferiore. Allora:
{ 1 , inf(a,b) = 0p
µ(y) =
0 , altrimenti

Dimostrazione:

µ (y) = - µ (z)
z<y

= - ( µ (a) + µ (b) + µ (z))
a,bz<y

= - µ (a) - µ (b) - ( µ (z)+ µ (z)- µ (z))
z<a z<b z<a,b
= - µ (a) - µ (b) - ( - µ (a) - µ (b) - µ (z))
zinf(a,b)
= - µ (a) - µ (b) + µ (a) + µ (b) + µ (z)
zinf(a,b)
= µ (z)
zinf(a,b)
= µ (inf(a,b)) + µ (z)
z<inf(a,b)

inf(a,b) = 0p : µ (y) = µ (inf(a,b)) = µ (0) = 1
inf(a,b) 0p : µ (y) = 1 + µ (z) = 0
z<inf(a,b)

2 Polinomio caratteristico

Sia P in IPO per cui valga la Chain Condition, di altezza h(P) = n.
Si dice Polinomio caratteristico di P:

(P;t) = µ (x) · t n-r(x)
xP
Il polinomio caratteristico è cioè un polinomio in t di grado n, in cui il coefficiente del termine
t s è il numero di elementi aventi lo stesso rango n-s moltiplicato
per il valore della funzione di Moebius di tali elementi.

Numeri di Whitney di prima specie:

w k = µ (x) ; 0k n
r(x)=n-k

Usando i numeri di Whitney di prima specie il polinomio caratteristico di un IPO P può essere scritto come:

n
(P;t) = w k (x) · t k
k=0

Casi in cui è facile calcolare il polinomio caratteristico

Caso 1


(P;t) = t · (H;t)


Dimostrazione

µ(x) = µ'(x) x H
µ(y) = 0 (lemma 1: y copre solo a e a 0p)
µ(1) = 0 (lemma 2: 1 copre 1' e y, e inf(1',y) 0p)

w n+1 = 1 = w' n (poiché è monico)
w n = w' n-1 = numero di atomi
(atomo = elemento che copre lo zero)

(P;t) = t n+1 + w' n-1 · t n + ... + w' 1 · t 2 + ( w' 0 + µ(y))·t + µ(1)
= t ( t n + w' n-1 · t n-1 + ... + w' 1 · t) + ( w' 0 + 0) ·t + 0
= t ( t n + w' n-1 · t n-1 + ... + w' 1 · t) + w' 0 ·t
= t · (H;t)

Caso 2: espansione booleana

r(x') = r(x) + 1 , per ogni x

P = H sfalsato di rango, dove ogni elemento di P è collegato al suo omologo in H.
Sia G il nuovo grafo così ottenuto.

(G;t) = (t-1) · (H;t)


Dimostrazione

Sia µ' la funzione di Moebius di H.

µ(y) = µ'(y) y H

Sia y omologo in P di 0H: µ(y) = - µ'(0H) = -1

se x H e x' è il suo omologo in P, x' 0H:

µ (x') = - µ (z)
z<x'

= - ( µ (z) + µ (z))
zx zx
z<x'

= - ( µ (z) + µ (x) + µ (z))
z<x zx
z<x'

= - ( - µ (x) + µ (x) + µ (z))
zx
z<x'

= - µ (z) = -µ'(x)
zx
z<x'

w n+1 = 1 = w' n (poiché è monico)
w n = w' n-1 - w' n
w n-1 = w' n-2 - w' n-1
...

(G;t) = t n+1 + ( w' n-1 - w' n ) · t n + ( w' n-2 - w' n-1 ) · t n-1 + ... + ( w' 0 - w' 1 ) · t
= t n+1 + w' n-1 · t n + ... + w' 0 · t - w' n ·t n - ... - w' 1 ·t - w' 0
= t ( t n + w' n-1 · t n-1 + ... + w' 0 ) - ( t n + w' n-1 · t n-1 + ... + w' 0 )
= (t - 1) · (H;t)



Caso 3


P, P' = H sfalsato di rango, dove ogni elemento di P e P' è collegato al suo omologo in H.
Si aggiunga poi un nuovo nodo e lo si colleghi ai nodi 1P e 1P'
Sia G il nuovo grafo così ottenuto.

(G;t) = t · (t-2) · (H;t)



Caso 4

Sia Pn il reticolo delle partizioni di un insieme di n elementi, dove gli elementi di rango k sono le partizioni in n-k blocchi dell'insieme.
Aggiungiamo l'elemento n+1esimo in ogni partizione in un blocco a se stante.
Sia P'n il grafo così ottenuto.

Consideriamo l'espansione booleana di P'n nella quale l'omologo di ogni elemento di P'n è ottenuto ponendo l'elemento n+1esimo nello stesso blocco in cui si trova il primo elemento.
Gli elementi di rango K dell'espansione booleana di P'n diventano allora alcune delle partizioni di un insieme di n+1 elementi in n+1-k blocchi.

esp(P'n) = sottoreticolo di Pn+1

(esp(P'n);t) = (t-1) · (P'n;t)


Esempio: n=3


(esp(P'3);t) = (t-1) · (P'3;t)
= (t-1) · (t²-3t+2)


In generale si ha:

(esp(P'n);t) = (t-k) · (P'n;t)


dove per esp(P'n) si intende il grafo che ha come nodi le partizioni dell'insieme di n+1 elementi nelle quali l'elemento n+1 può stare da solo oppure solamente insieme ai primi k elementi.


Torna all'indice