Dan Guyer, University of Washington
-
PDL C-401 and via Zoom Link: https://washington.zoom.us/j/91547335974
Abstract:
Motivated by trying to understand the behavior of the simplex method, Athanasiadis-De Loera-Zhang provided upper and lower bounds on the number of the monotone paths on 3-polytopes. For simple 3-polytopes with \$2n\$ vertices, they showed that the number of monotone paths is bounded above by \$(1+\varphi)^n\$, with \$\varphi\$ being the golden ratio. We improve the result and show that for a larger family of graphs the number is bounded above by \$1.6779^n\$ times some universal constant. Meanwhile, the best known construction and conjectured extremizer is approximately \$\varphi^n\$.
Note: There is no pre-seminar.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974