Diameter and Coherence of Monotone Path Graph
2015-05
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Diameter and Coherence of Monotone Path Graph
Authors
Published Date
2015-05
Publisher
Type
Thesis or Dissertation
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.
Description
University of Minnesota Ph.D. dissertation. May 2015. Major: Mathematics. Advisor: Victor Reiner. 1 computer file (PDF); ix, 93 pages.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Edman, Robert. (2015). Diameter and Coherence of Monotone Path Graph. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/175426.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.