Calendar

By a result of Agol and Guéritaud, a transitive pseudo-Anosov flow F on a closed three-manifold N, along with a certain collection O of its closed orbits, determines a veering triangulation V of N - O that encodes F. Together with Henry Segerman, we devised and implemented an algorithm that takes as an input V and a closed orbit c of F that is not in O, and returns a veering triangulation of N - O - c that also encodes F. I will discuss the main ideas behind the algorithm, its key challenges, and its role in collecting experimental evidence for certain conjectures about pseudo-Anosov flows.

This talk will survey the extremal theory of pattern-avoiding 0-1 matrices, and some of their applications in geometry, combinatorics, and algorithms.  If P is a 0-1 matrix, Ex(P,n) is the maximum number of 1s in an n x n 0-1 matrix that does not contain any submatrix that dominates P.  Every 0-1 pattern P can be regarded as the incidence matrix of a bipartite graph, in which the two sides of the bipartition are ordered.  Thus, this definition can be seen as a generalization of the Turan extremal function (for subgraph avoidance).

Pattern-avoiding 0-1 matrices have been studied since the late 1980s, and yet the precise relationship between 0-1 matrices and Turan theory is still poorly understood.  For many years the foremost open problem has been to characterize the extremal functions of acyclic patterns (those whose graphs correspond to forests).  In 2005 Pach and Tardos conjectured that Ex(P,n) = O(n polylog(n)), for any acyclic P.  We give a simple refutation of the Pach-Tardos conjecture by giving a class of acyclic patterns for which Ex(P,n) > n 2^{sqrt{log n}}.