MCCN X

Giovedì scorso ho spiegato qualcosa sui grafi casuali. Questi sono variabili aleatorie con valori in insiemi di grafi; di solito vengono realizzati utilizzando un qualche tipo di algoritmo casuale.

Faccio un esempio: disegnate N nodi su un foglio e scegliete un valore p fra 0 e 1, che rappresenta la connettività attesa del grafo.

Per ogni lato possibile (sono 0.5N(N+1), quindi prendetevi un po' di tempo) estraete un numero casuale uniformente distribuito tra 0 e 1. Se non avete un generatore di numeri casuali a portata di mano (basta Excel) scegliete un numero fra 1 e 6 al posto di p, e tirate un dado. Se questo numero è minore di p, disegnate il lato che state esaminando. Altimenti no. Il disegno che ottenete dopo aver tirato per tutti i possibili lati è un grafo casuale alla Erdös-Renyi.

La cosa interessante: c'è gente che afferma che le connessioni cerebrali sono, più o meno, un grafo casuale di questo tipo.

numeri primi (II)

végre nem butulok tovább

paul erdős

stavo per scrivere un post per commentare un post di un altro blogger, molto piú bravo di me (von wegen: autoreferenzialitá della blogosfera), quando sono stato vittima di un blitzkrieg del mio compagno di stanza, il mai troppo lodato r. n. che mi ha presentato una divertente dimostrazione dell'inifinitá dei numeri primi.

Teorema

Sia P={p in N, tale che p é primo}. Allora vale #(P)=infinito.

Dimostrazione

L'idea é quella di introdurre un'opportuna base topologica B sull'insieme degli interi Z. Sia per a intero e n naturale strettamente maggiore di 0 B(a,n):={a+kn: k intero} la progressione aritmetica di origine a e ragione n. Si noti che B:={B(a,n): a in Z, n in N*} definisce una base topologica, dato che l'intersezione di due progressioni aritmetiche é essa stessa una progressione aritmetica. Sia T la topologia generata da B, cioé l'insieme di tutte le possibili unioni di elementi di B. Essa ha le tre seguenti proprietá:
1) Dato che ogni progressione aritmetica é infinita, allora se O é un aperto di T, allora O é vuoto o ha inifiniti elementi.
2) Ogni elemento B(a,n) della base di O é anche chiuso. Infatti si ha B(a,n)=(B(a+1,n) U B(a+2,n) U B(a+n-1,n))^C, dove ^C indica l'operazione di complementazione. B(a,n) é quindi chiuso in quanto complemento di un'unione di insieme aperti.
3) Si consideri l'insieme A, unione di tutti i B(0,p), dove p é primo. Allora vale: A aperto in quanto unione di aperti. Inoltre A = Z\{-1,1}, dato che 1,-1 sono gli unici numeri senza fattori primi.
Supponiamo adesso che ci siano solo un numero finito di primi. Allora A sarebbe un insieme chiuso in quanto unione finita di chiusi. Il suo complemente A^C é quindi aperto e quindi o é vuoto, o possiede infiniti elementi. Avendo precedentemente dimostrato che A^C={-1,1}, otteniamo un assurdo.

il Libro e i sottobicchieri

per farvi capire che tipo e´ il mio prof vi vorrei raccontare un aneddoto. conoscete erdos? per lo meno di nome? beh, era un geniale matematico ungherese (1913-1996). ha scritto centinaia di articoli. fondato la teoria dei grafi casuali. dimostrato senza analisi complessa il teorema sulla distribuzione dei numeri primi. insomma, un geniaccio. chiamava le dimostrazioni meravigliose che ogni tanto si incontrano in matematica "dimostrazioni dal Libro". intendendo col Libro la lista delle dimostrazioni perfette in possesso di dio. non che ci credesse, in dio, parliamoci chiaro. ma per i matematici, diceva, e´ necessario credere nel Libro.

il mio prof (che non e´ erdos, pero´ e´ bravo comunque) le chiama "dimostrazioni da sottobicchieri" (bierdeckel in tedesco) perche´ possono essere eseguite in un pub, in tre righe, su un sottobicchiere.

non vi immaginate un tedesco birraiolo: e´ solo che non ama le cose troppo pompose.