Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Cecchetto, Federica (2017) Grafi expander. [Laurea triennale]

Per questo documento il full-text online non disponibile.

Abstract

I grafi expander sono una particolare tipologia di gra fi, la cui semplice esistenza sembra gi à controintuitiva: si tratta infatti di grafi che sono al contempo "sparsi" e "altamente connessi". I grafi expander sono stati introdotti da Bassalygo e Pinsker nei primi anni '70 e, da quel momento, oltre a rappresentare uno stimolante argomento di studio, hanno trovato applicazione in diversi settori della matematica e dell'informatica teorica (combinatorica, analisi funzionale, meccanica statistica e probabilit à, derandomizzazione, teoria dei codici, teoria della complessit à), oltre che nel disegno esplicito di algoritmi e reti con elevato grado di effi cienza. In questa tesi tratteremo le principali propriet à dei gra fi expander. Inoltre nella seconda parte riusciremo a costruire, con strumenti relativamente semplici, un esempio esplicito di grafo expander come grafo di Cayley di una famiglia di gruppi semplici lineari.

Item Type:Laurea triennale
Corsi di Laurea Triennale:pre 2012- Facoltà di Scienze MM. FF. NN. > Matematica
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/02 Algebra
Codice ID:56232
Relatore:Detomi, Eloisa M.
Data della tesi:07 July 2017
Biblioteca:Polo di Scienze > Biblioteca di Matematica

Solo per lo Staff dell Archivio: Modifica questo record