Bipartite Turán Problems for Ordered Graphs

Abstract

A zero-one matrix M contains a zero-one matrix A if one can delete some rows and columns of M, and turn some 1-entries into 0-entries such that the resulting matrix is A. The extremal number of A, denoted by ex(n,A), is the maximum number of 1-entries in an n×n sized matrix M that does not contain A. A matrix A is column-t-partite (or row-t-partite), if it can be cut along the columns (or rows) into t submatrices such that every row (or column) of these submatrices contains at most one 1-entry. We prove that if A is column-t-partite, then ex(n,A)<n2− 1 t + 1 t2 +o(1) , and if A is both column- and row-t-partite, then ex(n,A)<n2− 1 t +o(1). Our proof combines a novel density-increment-type argument with the celebrated dependent random choice method. Results about the extremal numbers of zero-one matrices translate into results about the Tur´an numbers of bipartite ordered graphs. In particular, a zero-one matrix with at most t 1-entries in each row corresponds to a bipartite ordered graph with maximum degree t in one of its vertex classes. Our results are partially motivated by a well-known result of F¨uredi (1991) and Alon, Krivelevich, Sudakov (2003) stating that if H is a bipartite graph with maximum degree t in one of the vertex classes, then ex(n,H) = O(n 2− 1 t ). The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs.