Expander Graphs i una aplicació a la informàtica

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.