2015/02/26 by Cooper, Joshua, Davis, Jeffrey · 1 citation
#05C50 #15B33 #92D15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1502.07450
We apply matrix theory over \mathbbF2 to understand the nature of so-called "successful pressing sequences" of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work.