an enticing game is to choose the basis so as to make the matrix as simple as possible.
paul halmos
qui avevo formulato una congettura. ebbene, tale congettura è falsa. Infatti vale il seguente lemma:
Lemma
La matrice di incidenza di un grafo è un operatore limitato su l^2 se e solo se il grafo è uniformemente localmente finito.
la dimostrazione è un calcolo semplice in ambo le direzioni (una la devo a d.m.). la cosa divertente è che tutto ciò ha lo stesso aroma del capitolo di "a hilbert space problem book" di halmos, nel capitolo dove discute di matrici infinite. in particolare assomiglia ad un lemma di toeplitz che afferma che se A è un operatore su l^2, allora esiste una rappresentazione matriciale dove ogni colonna contiene solo un numero finito di elementi diversi da 0.
ed anche oggi ho un intrattieni...
lunedì, novembre 26, 2007
giovedì, novembre 08, 2007
componente connessa (I)
quant'è bella giovinezza che si fugge tuttavia!
lorenzo de'medici
in risposta ad un mio amico barese, ecco qua una spiegazione visiva del significato del termine "componente connessa".
immaginiamo di vivere in un arcipelago di isole, collegate tra loro da ponti, ognuno dei quali è percorso da una strada a doppio senso. l'isola dove noi viviamo si chiama aaaahh. un giorno prendiamo la macchina e ci avviamo per il primo ponte che incontriamo, che si chiama uuunnno. per semplicità, supponiamo che l'unica strada interna alle isole sia una litoranea percorribile solo in senso orario, cosicchè esiste un unico primo ponte che si incontra partendo da un qualsiasi punto della strada. prima di attraversare il ponte disegniamo su un foglietto un punto rappresentante l'isola e una linea per il ponte.
attraversiamo questo ponte ed arriviamo su di una seconda isola, l'isola di bbbbee. nuovamente cerchiamo il primo ponte, che chiamiamo ddueeee. potrebbe essere quello da cui siamo appena arrivati, nel caso ci sia un solo ponte per bbbbee. in questo caso facciamo sul nostro foglietto una croce su bbbbee, per segnarci che abbiamo percorso tutti i ponti, e torniamo a aaaahh, a prendere il successivo ponte. nell'altro caso, segniamo sulla carta prendiamo il ponte ddueeee e proseguiamo per andare all'isola di cccì.
li proseguiremo questa operazione in un'ovvia progressione; alla fine avremo solo isole segnate da croci sulla nostra carta: quella che vediamo disegnata è una componente connessa del grafo delle isole.
le altre le possiamo trovare volando con l'aereo su un'altra isola e ricominciando il gioco...
lorenzo de'medici
in risposta ad un mio amico barese, ecco qua una spiegazione visiva del significato del termine "componente connessa".
immaginiamo di vivere in un arcipelago di isole, collegate tra loro da ponti, ognuno dei quali è percorso da una strada a doppio senso. l'isola dove noi viviamo si chiama aaaahh. un giorno prendiamo la macchina e ci avviamo per il primo ponte che incontriamo, che si chiama uuunnno. per semplicità, supponiamo che l'unica strada interna alle isole sia una litoranea percorribile solo in senso orario, cosicchè esiste un unico primo ponte che si incontra partendo da un qualsiasi punto della strada. prima di attraversare il ponte disegniamo su un foglietto un punto rappresentante l'isola e una linea per il ponte.
attraversiamo questo ponte ed arriviamo su di una seconda isola, l'isola di bbbbee. nuovamente cerchiamo il primo ponte, che chiamiamo ddueeee. potrebbe essere quello da cui siamo appena arrivati, nel caso ci sia un solo ponte per bbbbee. in questo caso facciamo sul nostro foglietto una croce su bbbbee, per segnarci che abbiamo percorso tutti i ponti, e torniamo a aaaahh, a prendere il successivo ponte. nell'altro caso, segniamo sulla carta prendiamo il ponte ddueeee e proseguiamo per andare all'isola di cccì.
li proseguiremo questa operazione in un'ovvia progressione; alla fine avremo solo isole segnate da croci sulla nostra carta: quella che vediamo disegnata è una componente connessa del grafo delle isole.
le altre le possiamo trovare volando con l'aereo su un'altra isola e ricominciando il gioco...
sabato, novembre 03, 2007
buona notte
dolce e chiara è la notte e senza vento,
e queta sovra i tetti e in mezzo agli orti
posa la luna, e di lontan rivela
serena ogni montagna.
g. leopardi
premesso che non sono costretto a "gettarmi a terra, gridare e fremere" come il buon giacomo (anzi, oggi ho anche rifiutato un invito al rockside della mia graziosa coinquilina), ammetto che ho passato tutta la serata a fare conti.
con questi risultati.
Congettura
La matrice di di incidenza di un grafo è un operatore limitato su l^2 se e solo se il grafo contiene O(k) nodi di grado k.
Dimostrazione
Speriamo domani.
PS: se qualcuno fosse infastidito dalla notazione con O(k): vuol dire semplicemente che il limite superiore del numero dei nodi di grado k diviso k è minore di infinito.
e queta sovra i tetti e in mezzo agli orti
posa la luna, e di lontan rivela
serena ogni montagna.
g. leopardi
premesso che non sono costretto a "gettarmi a terra, gridare e fremere" come il buon giacomo (anzi, oggi ho anche rifiutato un invito al rockside della mia graziosa coinquilina), ammetto che ho passato tutta la serata a fare conti.
con questi risultati.
Congettura
La matrice di di incidenza di un grafo è un operatore limitato su l^2 se e solo se il grafo contiene O(k) nodi di grado k.
Dimostrazione
Speriamo domani.
PS: se qualcuno fosse infastidito dalla notazione con O(k): vuol dire semplicemente che il limite superiore del numero dei nodi di grado k diviso k è minore di infinito.
Iscriviti a:
Post (Atom)
