Résumé - Arbres de dépliage co-compactes

Arbres de dépliage co-compactes

2025-07-10 07:49:40

{"Roman Gorazd"}

{math.CO,math.GR,"05E16, 05E18"}

Ce document de Roman Gorazd se concentre sur le concept d'arbres cocompacts dans l'étude des groupes agissant sur les arbres. Un arbre cocompact est un arbre où le groupe d'automorphismes, lorsqu'il agit sur l'arbre, a seulement un nombre fini d'orbits. Le document vise à déterminer quand un arbre de chemin racinaire d'un graphe orienté racinaire fini a un arbre d'extension cocompacte, qui est un voile universel du graphe. L'auteur introduit un type de coloriage de sommets appelé "réel" et montre que tout graphe admettant un tel coloriage a un arbre d'extension cocompacte. De même, tout graphe sans extrémité avec un arbre d'extension cocompacte peut être colorié réellement. Ce résultat est une étape significative vers la réponse à la question (1) de [5], qui demande la classification des graphes qui se déplient en un arbre cocompact. Le document définit le concept d'arbre d'extension et fournit un algorithme pour déterminer si un graphe se déplie en un arbre cocompact. L'algorithme implique de construire une modification du graphe qui change la racine de l'arbre d'extension et puis de vérifier si le graphe résultant a un coloriage réel. L'auteur explore également la relation entre le coloriage réel et les arbres d'extension cocompacts. Ils montrent que si un graphe a un coloriage réel, son arbre d'extension est cocompact, et de même, tout graphe avec un arbre d'extension cocompact a un coloriage réel. Le document discute également de la construction d'un graphe canonique à partir d'un arbre racinaire cocompact, qui est le graphe obtenu en identifiant les sommets de la même classe d'isomorphisme sous une relation d'équivalence non réduisant les arêtes. L'auteur montre que les étiquettes utilisées dans cette construction satisfont les propriétés d'un coloriage réel. Le document fournit une classification des graphes qui se déplient en arbres cocompacts, basée sur la structure de l'arbre d'extension du graphe. L'auteur montre que un graphe se déplie en un arbre cocompact si et seulement s'il a un coloriage réel. Enfin, le document discute du concept d'arbres presque isomorphes aux arbres cocompacts et fournit un algorithme pour vérifier si un arbre est presque isomorphe à un arbre cocompact. Cet algorithme implique de construire un produit de filet robuste et de vérifier s'il est presque isomorphe à l'arbre d'extension d'un arbre cocompact. Dans l'ensemble, le document offre une étude complète des arbres cocompacts et de leurs relations avec les graphes, et il propose une nouvelle approche pour classifier les graphes en fonction de leurs arbres d'extension.