Probabilités et logique : lois du 0-1 et lois de convergence pour les graphes aléatoires

Date/heure
9 février 2023
09:15 - 10:15

Lieu
Salle de conférences Nancy

Oratrice ou orateur
Valentin Feray (IECL)

Catégorie d'évènement
Groupe de travail Probabilités et Statistique

Résumé

Nous nous intéressons ici au modèle de graphes aléatoires d’Erdos-Renyi G(n,p), où les sommets sont étiquetés de 1 à n et chaque arête est prise indépendamment avec probabilité p. Un type de question classique sur ce modèle consiste à demander si une propriété $\varphi$ — par exemple, « le graphe contient un triangle » ou « le graphe est connexe » — est satisfaite ou non à la limite ; ou de manière plus générale, quelle est la limite de la probabilité que $G(n,p)$ vérifie $\varphi$ ? En prenant du recul, on peut se demander, si, quand $\varphi$ est une propriété « naturelle » (dans un sens que l’on précisera), cette limite existe toujours et si elle peut prendre n’importe quelle valeur (ou par exemple seulement 0 ou 1). Ceci amène à la notion de loi de convergence (si la limite existe toujours) ou de loi de 0/1 (si la limite vaut toujours 0 ou 1).

Je présenterai quelques résultats de ce type (pour G(n,p) et pour un modèle d’arbres aléatoires), et essayerai d’expliquer les idées derrière, venant de la théorie des modèles finis (en particulier le jeu combinatoire d’Ehrenfeucht-Fraïssé), de l’algorithmique (techniques de réduction en complexité) et de la combinatoire analytique (universalité des singularités en racine dans les modèles d’arbres).

(Basé sur le livre « Strange logic of random graphs », Spencer, 2001, et l’article de Woods « Colouring Rules for Finite Trees and Probabilities of Monadic Second Order Sentences », 1997).
Ce groupe de travail s’articule sur deux séances : celle ci est la deuxième partie.