Pseudo Randomness dans les graphiques

Cette séance de cours explore le concept de pseudo-aléatoire dans les graphes, en se concentrant sur la caractérisation en utilisant des valeurs propres de la matrice d'adjacence pour les graphes D-réguliers. La discussion s'étend à la construction de graphiques avec des valeurs propres non triviales situées dans une plage spécifique, connue sous le nom de graphiques de Ramanujan. L'instructeur explore l'approche probabiliste en utilisant la matrice laplacienne pour atteindre le pseudo-aléatoire, en soulignant l'importance des racines groupées dans les polynômes. La séance de cours progresse vers l'application du lemme déterminant de matrice pour comprendre le comportement des polynômes caractéristiques lors de l'ajout de matrices de rang un. Le concept d'entrelaceurs communs dans les polynômes est introduit, conduisant à des idées sur l'outil combinatoire probabiliste pour analyser les valeurs propres des matrices aléatoires.