ACO Seminar - Seth Pettie May 1, 2025 3:00pm — 4:00pm Location: In Person - Wean Hall 8220 Speaker: SETH PETTIE , Professor of Computer Science and Engineering, Department of Electrical Engineering and Computer Science, University of Michigan https://web.eecs.umich.edu/~pettie/ Forbidden 0-1 Patterns and the Pach-Tardos Conjecture 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}}. 4:00 pm → Jane Street-sponsored Tea and Cookies in the Math Lounge Please bring own mug when possible. Event Website: https://aco.math.cmu.edu/abs-24-25/may1.html Add event to Google Add event to iCal
