Enseignement 2021-2022

M2 ENS Lyon Probabilités 2021-2022, Cours Graphes aléatoires

2ème semestre
Début des cours le 14/01. Vendredi de 13h30 à 16h30.
Cours (sauf changement de dernière minute) : 14/01, 21/01, 28/01, 04/02, 11/02, 18/02.

Le cours aura lieu en distantiel, le lien sera vous envoyé. Si vous voulez y participer et vous n'êtes pas dans le M2 Mathématique, veuillez m'envoyer un message. (The course will be held in English in case some students prefer so.)

Evaluation : Présentation des sujets, tentativement le 25/03, à partir de 13h (tentativement).
Résumé du contenu tentative et références
Lien vers le contenu de l'école d'été "Nice summer school on random walks and complex networks" (Nice, 8-9 Juillet 2019) Background knowledge / lecture notes
Sujets pour la présentation :
J. Balogh, R. Morris, W. Samotij: The method of hypergraph containers (3 personnes)
X. S. Cai, G. Perarnau: The giant component of the directed configuration model revisited (1 personne)
S. Chatterjee: Stein's method for concentration inequalities (1 personne)
N. Fountoulakis, M. Kang, T. Makai: Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs (2 personnes)
I. Hartarsky: U-bootstrap percolation: critical probability, exponential decay and applications (3 personnes)
A. Sarid: The spectral gap of random regular graphs (3 personnes)
G. Slade: The lace expansion and its applications (applied to percolation) (Chapter 10) (1 personne ; chapitre 9 est la base de chapitre 10, et il faut le comprendre, mais sans le présenter)
E. Surya, L. Warnke: On the concentration of the chromatic number of random graphs (1 personne)

Enseignement dans les années précdéntes

M2 ENS Lyon Probabilités 2020-2021, Cours Graphes aléatoires

2ème semestre
Début des cours le 03/02. Mercredi de 9h à 12h.
Cours (sauf changement de dernière minute) : 03/02, 10/02, 24/02, 03/03, 10/03, 17/03.

Si le cours aura lieu en présentiel, il aura lieu en salle du séminaire 2 au sous-sol, La Doua, Lyon 1. Si le cours aura lieu en distantiel, le lien sera vous envoyé. Si vous voulez y participer et vous n'êtes pas dans le M2 Mathématique, veuillez m'envoyer un message.
Résumé du 03/02 : Définition de G(n,p) et G(n,M). Propriétés de graphes, croissance de la fonction indicatrice d'une propriété croissante (exposition en 2 étapes), valeurs de seuil (théorème de Bollobás-Thomason), valeurs de seuil aigues, méthode du premier et deuxième moment
Résumé du 10/02 : Méthode des moments : contenir un triangle, contenir un sousgraphe H, connexité, bornes de Chernoff, intuition composante géante (processus de branchement)
Résumé du 24/02 : Preuve transition de phase pour composante géante, taille de clique maximale en G(n,1/2), inégalité de Janson
Résumé du 03/03 : inégalité d'Azuma et application au nombre chromatique et à clique maximale, inégalité de Talagrand et application à clique maximale, introduction du modèle de configuration
Résumé du 10/03 : distributions de cycles courts dans le modèle de configuration, introduction à la méthode des équations différentielles, switchings
Résumé du 17/03 : Graphes aléatoires géométriques : connexité, existence de composante géante, Hamiltonicité

Evaluation : Présentation des sujets, le 24/03, à partir de 13h.
Résumé du contenu et références
Lien vers le contenu de l'école d'été "Nice summer school on random walks and complex networks" (Nice, 8-9 Juillet 2019) Background knowledge / lecture notes
Sujets pour la présentation :
G. Slade: The lace expansion and its applications (Chapter 1-3) (2 personnes)
K. Adhikari, R. J. Adler, O. Bobrowski, R. Rosenthal: On the spectrum of dense random geometric graphs (3 personnes)
X. S. Cai, G. Perarnau: The giant component of the directed configuration model revisited (2 personnes)
O. Ben-Eliezer, D. Hefetz, G. Kronenberg, O. Parczyk, C. Shikhelman, M. Stojakovic: Semi-random graph process (3 personnes)
J. Balogh, R. Morris, W. Samotij: The method of hypergraph containers (3 personnes)
J. Kahn, G. Kalai, N. Linial: The influence of variables on Boolean functions (2 personnes)
J. Bourgain, J. Kahn, G. Kalai, Y. Katznelson, N. Linial: The influence of variables in product spaces (1 personne, juste si le papier avant est pris aussi)
E. Friedgut, G. Kalai: Every monotone graph property has a sharp threshold (2 personnes, juste si les deux papiers avant sont pris aussi)
R. Basu, A. Sly: Evolving voter model on dense random graphs (3 personnes)
J.-C. Mourrat, D. Valesin: Phase transition of the contact process on random regular graphs (2 personnes)
C. Cooper, R. Elsässer, H. Ono, T. Radzik: Coalescing random walks and voting on connected graphs (2 personnes)
R. I. Oliveira: On the coalescence time of reversible random walks (3 personnes)
P. Pralat, N. Wormald: Almost all 5-regular graphs have a 3-flow (1 personne)

M2 ENS Lyon Probabilités 2019-2020, Cours Graphes aléatoires

2ème semestre

Calendrier :

Début des cours le 22/01. Mercredi de 9h à 12h, Salle Fokko du Cloux, Lyon 1.
Cours (sauf changement de dernière minute) : 22/01, 29/01, 05/02, 12/02, 19/02, 26/02, 11/03, 18/03.

Présentation des sujets : 25/03 (en ligne suite à la fermeture de l'université).
Résumé du contenu et références
Lien vers le contenu de l'école d'été "Nice summer school on random walks and complex networks" (Nice, 8-9 Juillet 2019) Background knowledge / lecture notes
Résumé du 22/01 : Définition de G(n,p) et G(n,M). Propriétés de graphes, croissance de la fonction indicatrice d'une propriété croissante (exposition en 2 étapes), valeurs de seuil (théorème de Bollobás-Thomason), valeurs de seuil aigues
Résumé du 29/01 : Premier et deuxième moment, Propriétés : contenir un triangle, contenir un sousgraphe H, connexité, intuition composante géante (processus de branchement)
Résumé du 05/02 : Bornes de Chernoff, preuve composante géante, taille de clique maximale en G(n,1/2) (concentration sur 2 valeurs, concentration exponentielle avec inégalité de Janson)
Résumé du 12/02 : Nombre chromatique de G(n, 1/2), inégalité d'Azuma et application au nombre chromatique et à clique maximale, inégalité de Talagrand et application à clique maximale, début de valeur de seuil cycles Hamiltoniens
Résumé du 19/02 : existence de chemin longue pour G(n,p), valeur de seuil cycles Hamiltoniens en G(n,p)
Résumé du 26/02 : Modèle de configuration : distribution de cycles petits, connexité, Hamiltonicité (conditionnement sur des cycles petits) ; introduction à la méthode des équations différentielles
Résumé du 11/03 : la méthode des équations différentielles, introduction aux graphes aléatoires géométriques, connexité des graphes aléatoires géométriques
Résumé du 18/03 (en ligne suite à la fermeture de l'université) : graphes aléatoires géométriques (connexité, composante géante, Hamiltonicité), introduction aux graphes alétoires hyperboliques (composante géante, distribution des degrés)


Sujets pour la présentation :
F. Joos, G. Perarnau: Critical percolation on random regular graphs
C. Cooper, A. Frieze: The cover time of random geometric graphs
B. Bollobás, O. Riordan, J. Spencer, G. Tusnády: The degree sequence of a scale-free random graph process
A. Frieze: On the value of a random minimum spanning tree problem
A. Frieze, X. Pérez-Giménez, P. Prałat: Perfect matchings and Hamiltonian cycles in the preferential attachment model
C. Bordenave, G. Lugosi, N. Zhivotovskiy: Noise sensitivity of the top eigenvector of a Wigner matrix
J. Jonasson: On the cover time for random walks on random graphs
C. Cooper, A. Frieze, T. Radzik: Multiple random walks in random regular graphs
A. Goel, S. Rai, B. Krishnamachari: Monotone properties of random geometric graphs have sharp thresholds
O. Angel, R. van der Hofstad, C. Holmgren: Limit laws for self-loops and multiple edges in the configuration model