Graphes dans les surfaces et ergodicité topologique

Résumé La façon la plus simple de faire d’un graphe fini connexe G un système dynamique est de lui donner une polarisation, c’est-à-dire un ordre cyclique des arêtes incidentes à chaque sommet. L’espace de phase script upper P left parenthesis upper G right parenthesis $\mathcal {P}(G)$ P ( G ) d’un graphe consiste en toutes les paires left parenthesis v comma e right parenthesis $(v,e)$ ( v , e ) où v est un sommet et e une arête incidente à v . Elle donne donc la position et le vecteur initiaux. Une telle condition est équivalente à une arête que l’on munit d’une orientation e Subscript script upper O $e_{\mathcal O}$ e O . Avec la polarisation, chaque donnée initiale mène à une marche à gauche en tournant à gauche à chaque sommet rencontré, ou en rebondissant s’il n’y a en ce sommet aucune autre arête. Une marche à gauche est appelée complète si elle couvre toutes les arêtes de G (pas nécessairement dans les deux sens). Nous définissons la valence d’un sommet comme le nombre d’arêtes adjacentes à ce sommet, et la valence d’un graphe comme étant la moyenne des valences de ses sommets. Dans cet article, nous démontrons que si un graphe plongé dans une surface orientée fermée de genre g possède une marche à gauche complète, alors sa valence est d’au plus 1 plus StartRoot 6 g plus 1 EndRoot $1 + \sqrt {6g+1}$ 1 + 6 g + 1 . Nous prouvons de plus que ce résultat est optimal pour une infinité de genres g et qu’il est asymptotiquement optimal lorsque g right arrow plus infinity $g \to + \infty $ g → + ∞ . Cela mène à des obstructions pour les plongements de graphes sur une surface. Puisque vérifier si un graphe polarisé possède ou non une marche à gauche complète s’opère en temps au plus 4 upper N $4N$ 4 N , où N est le nombre d’arêtes (il

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.