IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

A new Characterization of V-Posets

  • Nov. 9, 2018
  • 2:30 p.m.
  • LeConte 317R

Abstract

Recently, Misanantenaina and Wagner characterized the set of induced $N$-free and bowtie-free posets as a certain class of recursively defined subposets which they term "$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 $U^TU$ 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 information and the forbidden subposet characterization, and we discuss a few open questions that arise in connection with these posets.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC