Speaker
Description
Pressing sequences of simple undirected graphs totally colored by a field arise naturally in computational phylogenetics, where (over $GF(2)$) they are in bijection with sortings-by-reversal of signed permutations which model gene sequences in related organisms. They can be viewed in several surprising different ways, including as any consecutive initial sequence of rows whose diagonal elements can serve, in natural order, as the pivots of Gaussian elimination performed on a symmetric matrix over the chosen field, with the caveat that every pivot entry is a nonzero square. This gives rise to their connection with positivity: for example, a symmetric matrix $M$ is positive definite iff the graph of which it is the (colored) adjacency matrix is ``pressable'' in the order given by the rows of $M$. Thus, finding such an ordered basis of the row space with this property is a natural question, and one for which we have a simple polynomial time algorithm when the base field is $GF(2)$. However, the only algorithms known for fields of characteristic greater than $2$ have time complexity $O(n!)$ where $n$ is the number of vertices in the graph (and the dimension of the corresponding matrix). We discuss progress on this question and future directions.