Mathematics Computer Science Seminar
Joshua Cooper
University of South Carolina
Graph Pressing Sequences and Binary Linear Algebra
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) 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.
Please note the unusual time and room.
Monday October 23, 2017 at 10:00 AM in SEO 612