Graphes polaris\'es et ergodicit\'e topologique

arXiv2209.00516MaRDI QIDQ6409482FDOQ6409482

François Lalonde, Jordan Payette, Dustin Connery-Grigg

Publication date: 1 September 2022

Abstract: The simplest way to make a dynamical system out of a finite connected graph $G$ is to give it a polarization, that is to say a cyclic ordering of the edges incident to a vertex, for each vertex. The phase space $T(G)$ then consists of all pairs $(v,e)$ where $v$ is a vertex and $e$ is an edge incident to $v$. Such an initial condition gives a position and a momentum. The data $(v,e)$ is of course equivalent to an edge endowed with an orientation $e_{mathcalO}$. With the polarization, each initial data leads to a leftward walk defined by turning left at each vertex, or making a rebound if there is no other edge. A leftward walk is called complete if it goes through all edges of $G$, not necessarily in both directions. As usual, we define the valence of a vertex as the number of edges incident to it. We say that a graph has valence at least $V$ if the valence of each vertex is at least $V$. In this article, we prove that if a graph is embedded in a closed oriented surface of genus $g$, of valence at least $3g+3$, then this graph admits no complete leftward walk. For genus $g=0,1$, we get sharp results. This leads to obstructions for the embeddability of graphs on a surface. Since checking that a polarized graph admits a complete leftward walk or not is done in time $4N$, where $N$ is the cardinality of the edges (we just have to check it on both orientations of any given edge), this obstruction is particularly efficient in terms of computability. This is the first obstruction for such a deep problem which is linear in computation time.

Mathematics Subject Classification ID

General topics of discrete mathematics in relation to computer science (68R01) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Singular homology and cohomology theory (55N10) Embeddings and immersions in PL-topology (57Q35) Dynamics in general topological spaces (37B02)

This page was built for publication: Graphes polaris\'es et ergodicit\'e topologique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6409482)