Cette thèse explore les structures locales en combinatoire, en se concentrant sur la compréhension de la façon dont les configurations locales influencent les propriétés et les structures globales des objets combinatoires. Cette thèse est divisée en quatre parties, chacune examinant différents problèmes liés aux structures locales : reconstruction de la distance, saturation du poset, encastrement de l'étalement et structures universelles.
Dans le chapitre relatif à la reconstruction des distances, nous cherchons à reconstruire un graphe inconnu à l'aide d'informations locales. Nous n'avons accès qu'à un oracle fournissant les distances de plus court chemin entre les paires de sommets.
Nous étudions ce problème pour différentes classes de graphes, en améliorant les bornes inférieures et supérieures les plus connues dans différents cas. En particulier, nous fournissons un algorithme optimal pour reconstruire les arbres et un algorithme quasi-optimal pour reconstruire les graphes sans longs cycles induits.
Ensuite, nous étudions la saturation des posets, introduite par Katona et Tarjan en 1981. Ce concept prolonge les travaux fondateurs de Turán dans la théorie des graphes extrémaux. Une famille saturée P est une famille maximale qui évite toute sous-structure localement isomorphe à P (c'est-à-dire qui évite P en tant que sous-ensemble induit). Nous étudions le nombre de saturation d'un poset P, défini comme la taille minimale d'une famille saturée P incluse dans l'hypercube de dimension n. Malgré un travail substantiel sur ce problème ces dernières années, le nombre de saturation n'est connu exactement que pour les petits posets, et ses comportements possibles sont encore largement inconnus. Dans cette thèse, nous montrerons qu'une extension d'un lemme de Lehman et Ron nous permet de calculer exactement le nombre de saturation de l'antichaîne de taille k. Nous prouverons également la première borne supérieure générale sur le comportement possible du nombre de saturation pour n'importe quel poset P.
Dans le chapitre sur l'étendue, nous étudions la distribution des arbres couvrants dans les graphes denses. Cela peut sembler, à première vue, loin d'être local, puisqu'une structure « couvrante » est par définition globale, mais la technique clé que nous avons développée pour construire ces structures couvrantes globales passe par la subdivision en de multiples sous-structures locales. Grâce à cette nouvelle méthode, nous sommes en mesure de fournir une preuve plus simple et plus souple de l'existence d'encastrements étalés pour les arbres à degré borné. En particulier, notre approche n'utilise pas le lemme de régularité de Szemerédi.
Enfin, nous étudions les structures universelles. Etant donné une famille F d'objets combinatoires et un entier n, un autre objet U est dit universel s'il contient chaque élément de F de taille n en tant que sous-structure locale. Nous appelons une telle structure "fidèle" lorsque U fait également partie de F. Dans ce chapitre, nous étudions la taille minimale des graphes universels fidèles pour les classes de graphes fermés mineurs ainsi que la taille des posets universels pour la famille de tous les posets.