Date of Award

Spring 2019

Document Type

Open Access Thesis

First Advisor

Joshua Cooper

Abstract

In 2016, Hasebe and Tsujie gave a recursive characterization of the set of induced N -free and bowtie-free posets; Misanantenaina and Wagner studied these orders fur- ther, naming them “V-posets”. Here we offer a new characterization of V-posets by introducing a property we refer to as autonomy. A poset P is said to be autonomous if there exists a directed acyclic graph D (with adjacency matrix U ) whose transitive closure is P, with the property that any total ordering of the vertices of D so that Gaussian elimination of UT U proceeds without row swaps is a linear extension of P. Autonomous posets arise from the theory of pressing sequences in graphs, a problem with origins in phylogenetics. The pressing sequences of a graph can be partitioned into families corresponding to posets; because of the interest in enumerating pressing sequences, we investigate when this partition has only one block, that is, when the pressing sequences are all linear extensions of a single autonomous poset. We also provide an efficient algorithm for recognition of autonomy using structural informa- tion and the forbidden subposet characterization, and we discuss a few open questions that arise in connection with these posets.

Rights

© 2019, Peter Gartland

Download

Included in

Mathematics Commons

Share

COinS