FONCTIONNELLES DE GRAPHES ALÉATOIRES ÉCHANTILLONNÉS À PARTIR D’UN GRAPHON

Un graphe simple (non orienté) G est un couple (V (G); E(G)) formé d’un ensemble V (G) paires non ordonnées de sommets. On note e(G) le nombre d’arêtes du graphe G. Rappelons qu’un graphe simple est un graphe sans boucles (un sommet n’est jamais relié à lui même) et sans arêtes multiples (deux sommets sont reliés par au plus une arête). Un graphe est fini si son nombre de sommets (et donc d’arêtes) est fini. Dans ce cas, en numérotant les sommets de 1 à v(G), on pourra identifier V (G) à [v(G)]. On considérera dans la suite des graphes finis simples (et non orientés). On note F l’ensemble des graphes finis simples (et non orientés).Ainsi, A est une matrice symétrique binaire avec des zéros sur la diagonale. On peut également associer à une matrice d’adjacence d’un graphe G son image pixelisée (« pixel picture » en anglais) : il s’agit du carré unité que l’on subdivise en petits carrés de longueur 1=v(G) ; les 0 sont remplacés par des carrés blancs et les 1 sont remplacés par des carrés noirs.) est dense (resp. creuse) si la suite de densités de ces graphes tend vers une constante strictement positive (resp. vers 0) quand n tend vers l’infini.

Graphes aléatoires

Nous allons maintenant considérer des graphes aléatoires. Les modèles de graphes aléa- toires les plus simples sont ceux d’Erdős et Rényi, introduits en 1959 1960. Rappelons qu’un graphe d’Erdős-Rényi G(p) à n sommets et de paramètre p avec 0 < p < 1, est un graphe aléatoire ayant pour ensemble des sommets [n] = f1; : : : ; ng et dont les arêtes existent de manière indépendante avec probabilité p. A partir des années 2000, d’autres modèles de graphes, plus complexes, ont été développés afin d’obtenir des graphes ayant des propriétés plus proches des réseaux réels. Parmi ces modèles figurent, par exemple, le modèle de configu- ration (modèle de graphes aléatoires où les degrés des sommets sont fixés) ou encore le modèle d’attachement préférentiel (modèle de graphes aléatoires dynamique, construits de manière récursive), voir Durrett [72] et van der Hofstad [187] pour de récents ouvrages de références.Dans cette partie, nous allons voir de manière informelle, quelle peut être la limite d’une suite de graphes au travers de deux exemples. Les exemples que nous développerons sont tirés de Borgs, Chayes, Lovász, Sós et Vesztergombi [37]. On considère une suite de graphes finis simples denses (G(1=2) est un graphe d’Erdős-Rényi de paramètre 1=2 à n sommets. Si l’on regarde la suite d’images pixelisées associées aux matrices d’adjacences, on peut remarquer une convergence « graphique » de cette suite d’images vers le carré unité uniformément gris, comme l’illustre l’image 2.2 ci-dessous. L’origine est placée dans le coin en haut à gauche afin d’être en accord avec la convention de numérotation des éléments matriciels.

Ainsi, on peut conjecturer que la suite de graphes (G ) « converge », en un sens que nous définirons dans la suite, vers le graphe infini dont la matrice d’adjacence correspond à la fonction constante égale à 1=2 sur [0; 1]ayant pour ensemble de sommets [n] se construit de manière itérative. On commence par un seul sommet. À chaque étape un nouveau sommet est crée et chaque paire de sommets non encore connectés à l’étape précédente est reliée avec probabilité 1=k où k est le nombre de sommets à l’étape actuelle (voir figure 2.3). On remarque encore une fois une convergence graphique des images pixelisées quand le nombre de sommets augmente, vers la fonction de deux variables W définie par W (x; y) = 1 max(x; y) pour tout x; y 2 [0; 1].Nous allons définir la notion d’homomorphismes qui permettra de donner une caractéri- sation de la convergence d’une suite de graphes denses. De nombreux paramètres de graphes peuvent s’exprimer à partir du nombre d’homomorphismes, voir Freedman, Lovasz et Schrij- ver [95] pour des exemples d’applications.