Close Menu

Graph Pressing Sequences and Binary Linear Algebra

When: 

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

Where: 

Rettaliata Engineering Center, Room 104

Speaker: 

Joshua Cooper
Department of Mathematics, University of South Carolina

Description: 

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