W&M Featured Events

This calendar presented by William & Mary

[PAST EVENT] Mathematics Colloquium: Xiaoya Zha (Middle Tennessee State University)

September 21, 2018
2pm - 3pm
Location
Jones Hall, Room 302
200 Ukrop Way
Williamsburg, VA 23185Map this location
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.

Contact

Anh Ninh