Xiaoya Zha

Non-revisiting Paths in Polyhedral Maps on Surfaces

Date: 4/27/2018
Time: 3:30PM-4:30PM
Place: 315 Armstrong Hall

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 varied 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 is closely related to

(i) the local connectivity $\kappa_G(x; y)$ (i.e. the number of disjoint paths between x and y);

(ii) the number of dfferent homotopy classes of (x; y)-paths;

(iii) the number of (x; y)-paths in each homotopy class.

For a given surface $\Sigma$, 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.

This is joint work with Michael Plummer and Dong Ye.

This talk will be accessible to graduate students.

Xiaoya Zha

All are welcome.

Date, Location: