Bipartite Turán Problems for Ordered Graphs

Abhishek Methuku, István Tomon

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)895-911
Number of pages17
JournalCombinatorica
Volume42
Issue number6
DOIs
StatePublished - Dec 2022
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Bipartite Turán Problems for Ordered Graphs'. Together they form a unique fingerprint.

Cite this