Urbana Campus Research Calendar (OVCRI)

Speaker: Abhishek Methuku (UIUC)

Title: Turán problems for ordered graphs and 0-1 matrices

Abstract:  A zero–one matrix M is said to contain another zero–one matrix A if we can delete some rows and columns of M and change some 1-entries to 0-entries so that the resulting matrix is A. The extremal number of A, denoted ex(n, A), is the maximum number of 1-entries an n×n zero–one matrix can have without containing A. The systematic study of this function for various patterns A goes back to work of Füredi and Hajnal (1992), and the area has many connections to other parts of mathematics and to theoretical computer science. For instance, one notable application is the celebrated proof of the Stanley–Wilf conjecture by Marcus and Tardos.
Much of the existing literature focuses on acyclic patterns, but comparatively little is known in the general case, when A need not be acyclic. In this talk, I will discuss several proof ideas that yield new results in this direction, including various results on Turán numbers of ordered cycles and an asymptotically tight general theorem showing that if A has at most t ones in every row, then ex(n, A) ≤ n^(2 − 1/t + o(1)), generalizing a celebrated result of Füredi and of Alon–Krivelevich–Sudakov on the (unordered) extremal number of bipartite graphs with maximum degree t in one part.
I will also survey several open problems in the area and discuss possible directions for future research. This talk is based on several joint works.