Cette thèse porte sur l'étude de modèles de parking dans un sens large sur de grands graphes et arbres aléatoires.

 

Dans un premier temps, nous étudions deux algorithmes permettant d'obtenir un grand ensemble indépendant d'un graphe, c'est-à-dire un sous-ensemble de sommets du graphe qui ne contient pas de paire de sommets voisins. Le premier utilise une stratégie gloutonne pour construire un ensemble indépendant maximal pour l'inclusion. L'ensemble ainsi obtenu a en général une densité positive et nous donnons des exemples de grands graphes (aléatoires) où l'on peut calculer exactement la loi de la taille de l'ensemble indépendant que l'on obtient. Le second algorithme est l'algorithme de Karp--Sipser, qui est optimal au sens où il existe un ensemble indépendant de taille maximale qui contient le sous-ensemble de sommet produit par l'algorithme. Cependant, cet algorithme s'arrête lorsque le sous-graphe inexploré ne contient plus de feuilles et on appelle alors ce sous-graphe le cœur de Karp--Sipser. Nous donnons la localisation de la transition de phase pour l'existence d'un cœur de Karp--Sipser géant pour un modèle de configuration avec des sommets de degrés 1, 2 et 3, et nous analysons précisément la taille de ce cœur au point critique.

 

Dans un second temps, nous nous intéressons au modèle de parking (dynamique) introduit par Konheim et Weiss dans le cas de la ligne. Dans cette version, on se place sur un arbre enraciné où chaque sommet représente une place de parking et les arêtes sont orientées vers la racine. Les voitures arrivent sur les sommets, se garent dès que possible en suivant les arêtes orientées et sortent de l’arbre par la racine si elles ne trouvent pas de place. On s’attend naturellement à observer une transition de phase. En effet, si peu de voitures arrivent, la plupart d’entre elles va pouvoir se garer tandis que si la densité de voitures est trop élevée, une proportion positive de voitures ne trouvera pas de place disponible et sortira par la racine de l’arbre. Nous formalisons d'abord l'existence de cette transition de phase pour une suite d'arbres qui converge vers une limite locale sous des hypothèses assez légères. Ensuite, nous en donnons la localisation pour des arbres de Bienaymé--Galton--Watson critiques en utilisant à nouveau la limite locale, et sur l'arbre binaire infini via des techniques combinatoires. Pour les arbres critiques, nous montrons également le caractère abrupte de la transition de phase. De plus, pour un modèle particulier d'arbres et d'arrivées de voitures, un couplage entre le modèle de parking et le modèle de graphe d' Erdős--Rényi nous permet notamment d'étudier la fenêtre critique de la transition de phase et fournit des informations sur les arbres de voitures garés.

 

Enfin, nous établissons un lien entre le modèle de parking et les cartes planaires via une décomposition combinatoire issue du parking vis-à-vis de la dernière voiture.