Document type
Bachelor thesisPublication date
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/216427
Expander Graphs i una aplicació a la informàtica
Journal Title
Authors
Director/Tutor
Journal ISSN
Volume Title
Related resource
Abstract
[ca] L'objectiu d'aquest treball és estudiar una construcció d'una família d'expander graphs i veu-re una aplicació a la informàtica. La part matemàtica del treball, defineix el que és una família d'expanders i després té 4 blocs: el primer dedicat a una visió més algebraica dels grafs, a partir de la seva matriu d'adjacència, per acabar donant un resultat que relaciona els valors propis d'aquesta matriu amb els expanders. El segon bloc dona alguns conceptes i resultats de teoria de nombres i el tercer defineix els grups $\left.P G L_{( } K\right)$ i $P S L_2(K)$, i dona algunes propietats interessants d'aquests. Finalment, al quart bloc, es fan servir els tres anteriors per donar una construcció explícita d'una família de grafs, coneguda com a grafs $X^{p, q}$, i acaba amb la demostració del fet que, efectivament, es tracta d'una família d'expanders. Després, a la part informàtica estudiarem l'aplicació dels mateixos a la propagació d'informació a través de xarxes neuronals de graf.
[es] The aim of this project is to study an explicit construction of a family of expander graphs, and give an application to computer science. The mathematical part of the project gives the definition of a family of expander graphs and then it has four main blocks: in the first one we will use Linear Algebra to define expander graphs using the eigenvalues of the adjacency matrix of the family graphs. The second block gives some definitions and results about Number Theory and the third one defines the $\left.P G L_{( } K\right)$ i $P S L_2(K)$, and also gives some interesting properties about those. Finally, the fourth block uses the previous ones to define a family of graphs known as $X^{p, q}$, and ends proving the fact that it actually is a family of expander graphs. Then, for the application, we will study an example on how expander graphs help with the propagation in Graph Neural Networks.
Description
Treballs Finals de Grau d'Enginyeria Informàtica, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2024, Director: Ignasi Mundet i Riera i Oriol Pujol Vila
Citation
Citation
MARISCAL VIZCAYA, Guillermo. Expander Graphs i una aplicació a la informàtica. [consulted: 17 of June of 2026]. Available at: https://hdl.handle.net/2445/216427