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(nA)<n2−1t+1t2+o(1) and if A is both column- and row-t-partite, then ex(nA)<n2−1t+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án 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üredi (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(nH)=O(n2−1t). The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs.
Original language | English (US) |
---|---|
Pages (from-to) | 895-911 |
Number of pages | 17 |
Journal | Combinatorica |
Volume | 42 |
Issue number | 6 |
DOIs | |
State | Published - Dec 2022 |
Externally published | Yes |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics