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)$ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mrow> <mml:mi mathvariant="script">P</mml:mi> <mml:mo stretchy="false" form="prefix" fence="true">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false" form="postfix" fence="true">)</mml:mo> </mml:mrow> </mml:math> d’un graphe consiste en toutes les paires left parenthesis v comma e right parenthesis $(v,e)$ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mrow> <mml:mo stretchy="false" form="prefix" fence="true">(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>e</mml:mi> <mml:mo stretchy="false" form="postfix" fence="true">)</mml:mo> </mml:mrow> </mml:math> 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}$ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:msub> <mml:mi>e</mml:mi> <mml:mi mathvariant="script">O</mml:mi> </mml:msub> </mml:math> . 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}$ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:msqrt> <mml:mrow> <mml:mn>6</mml:mn> <mml:mi>g</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> . 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 $ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mrow> <mml:mi>g</mml:mi> <mml:mo>→</mml:mo> <mml:mo>+</mml:mo> <mml:mo>∞</mml:mo> </mml:mrow> </mml:math> . 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$ <mml:math xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mnf="http://cambridge.org/core/manifest" xmlns:cup="http://contentservices.cambridge.org" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://cambridge.org/core/metadata" xmlns:core="http://cambridge.org/core" xmlns:c="http://cambridge.org/core/content" display="inline"> <mml:mrow> <mml:mn>4</mml:mn> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> , où N est le nombre d’arêtes (il

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.