[PAST EVENT] Mathematics Colloquium: Xiaoya Zha (Middle Tennessee State University)
Access & Features
- Open to the public
Title: Non-revisiting Paths in Polyhedral Map on Surfaces
Abstract: The Non-revisiting Path Conjecture (or Wv-path Conjecture) due to Klee and Wolfe states that any two vertices of a simple polytope can be joined by a path that does not revisit any facet. This is equivalent to the well-known Hirsch Conjecture. Klee conjectured even more, namely that the Non-revisiting Path Conjecture is true for all general cell complexes. Klee proved that the Non-revisiting Path Conjecture is true for 3-polytope (3-connected plane graphs). Later, the general Non-revisiting Path Conjecture was verified for polyhedral maps on the projective plane and the torus by Barnette, and on the Klein bottle by Pulapaka and Vince. However, a few years ago, Santos proved that the Hirsch conjecture is false in general.
In this talk, we show that the the non-revisiting path problem for polyhedral maps on surface is closely related to (i) the local connectivity (i.e. the number of disjoint paths between x and y; (ii) the number of different homotopy classes of (x, y)-paths; (iii) the number of (x, y)-paths in each homotopy class.
For a given surface, we give quantitative conditions for the existence of non-revisiting paths between x and y. We also provide more systematic counterexamples with high number (linear to genus of the surface) of paths between x and y but without any non- revisiting path between them. These results show the importance of topological properties of embeddings of underline graphs for this geometric setting problem.