Close Menu

Graph Pressing Sequences and Binary Linear Algebra


Oct 23, 2017 - 1:50pm to 2:55pm


Rettaliata Engineering Center, Room 104


Joshua Cooper
Department of Mathematics, University of South Carolina


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); a relation on pressing sequences that has a surprisingly diverse set of characterizations; and some open problems. 

Event Type: 

Department of Applied Mathematics - Colloquia