Graph Pressing Sequences and Binary Linear Algebra

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.