Non-self-touching paths in plane graphs

Abstract

A path in a graph $G$ is called non-self-touching if two vertices are neighbours in the path if and only if they are neighbours in the graph. We investigate the existence of doubly infinite non-self-touching paths in infinite plane graphs.
The matching graph $G_{\ast }$ of an infinite plane graph $G$ is obtained by adding all diagonals to all faces, and it plays an important role in the theory of site percolation on $G$. The main result of this paper is a necessary and sufficient condition on $G$ for the existence of a doubly infinite non-self-touching path in $G_{\ast }$ that traverses some diagonal. This is a key step in proving, for quasi-transitive $G$, that the critical points of site percolation on $G$ and $G_{\ast }$ satisfy the strict inequality $p_{\mathrm{c}}(G_{\ast })<p_{\mathrm{c}}(G)$, and it complements the earlier result of Grimmett and Li [Random Struct. Alg. 65 (2024) 832–856], proved by different methods, concerning the case of transitive graphs. Furthermore, it implies, for quasi-transitive graphs, that $p_{\mathrm{u}}(G)+p_{\mathrm{c}}(G)\ge 1$, with equality if and only if the graph $G_{\Delta }$, obtained from $G$ by emptying all separating triangles, is a triangulation. Here, $p_{\mathrm{u}}$ is the critical probability for the existence of a unique infinite open cluster.