Bipartite Tur\'an problems for ordered graphs

DOI10.1007/S00493-021-4296-0MaRDI QIDQ6323401arXivFDO

Authors Abhishe Methuku, István Tomon

Publication date 8 August 2019

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Combinatorics of partially ordered sets (06A07)

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 $nimesn$ 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)<n^{2-frac1t+frac12t^2+o(1)}$, and if $A$ is both column- and row-$t$-partite, then $ex(n,A)<n^{2-frac1t+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-frac1t})$. The aim of the present paper is to establish similar general results about the extremal numbers of ordered graphs.

This page was built for publication: Bipartite Tur\'an problems for ordered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323401)