Diameter and Coherence of Monotone Path Graph

Abstract

A Zonotope $Z$ is the linear projection of an $n$-cube into $\mathbb{R}^d$. Given a generic linear function $f$, an $f$-monotone path on $Z$ is a path along edges from the $f$-minimizing vertex $-z$ to its opposite vertex $z$. The monotone paths of $Z$ are the vertices of the monotone path graph in which two $f$-monotone paths are adjacent when they differ in a face of $Z$. In our illustration the two red paths are adjacent in the monotone path graph because they differ in the highlighted face. An $f$-monotone path is coherent if it lies on the boundary of a polygon obtained by projecting $Z$ to 2 dimensions. The dotted, thick, red path in Figure 0.1 (see pdf) is coherent because it lies on the boundary after projecting $Z$ to the page. However, there is no equivalent projection for the blue double path. The alternate red path may be coherent or incoherent based on the choice of $f$. The coherent $f$-monotone paths of $Z$ are a set of geometrically distinguished galleries of the monotone path graph. Classifying when incoherent $f$-monotone paths exist is the central question of this thesis. We provide a complete classification of all monotone path graphs in corank 1 and 2, finding all families in which every $f$-monotone path is coherent and showing that all other zonotopes contain at least one incoherent $f$-monotone path. For arrangements of corank 1, we prove that the monotone path graph has diameter equal to the lower bound suggested by Reiner and Roichman using methods of $L_2$-accessibility and illustrate that $L_2$ methods cannot work in corank 2 by finding a monotone path graph which has no $L_2$-accessible nodes. We provide examples to illustrate the monotone path graph and obtain a variety of computational results, of which some are new while others confirm results obtained through different methods. Our primary methods use duality to reformulate coherence as a system of linear inequalities. We classify monotone path graphs using single element liftings and extensions, proving for when $Z$ has incoherent $f$-monotone paths, then any lifting or extension of $Z$ has incoherent $f$-monotone paths too. We complete our classification by finding all monotone path graphs with only coherent $f$-monotone paths and finding a set of minimal obstructions which always have incoherent $f$-monotone paths.