IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Graph Pressing Sequences and Binary Linear Algebra, Updated

  • Oct. 13, 2017
  • 2:30 p.m.
  • LeConte 310

Abstract

One can construct a useful metric on genome sequences by computing minimal-length sortings of (signed) permutations by reversals. Hannenhalli and Pevzner famously showed that such sorting sequences are essentially equivalent to a certain sequences of operations -- ``vertex pressing'' -- on bicolored (aka loopy, aka simple pseudo-) graphs. We examine the matrix algebra over GF(2) that arises from the theory of such sequences, providing a collection of equivalent conditions for their existence and showing how linear algebra, poset theory, and group theory can be used to study them. We discuss enumeration, characterization, and recognition of uniquely pressable graphs (those with exactly one pressing sequence); relations on pressing sequences that have a surprisingly diverse set of characterizations; and some open problems. Joint work with Hays Whitlatch.

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