Bipartite Tur\'an problems for ordered graphs

DOI10.1007/S00493-021-4296-0arXiv1908.03189MaRDI QIDQ6323401FDOQ6323401

Authors: Abhishe Methuku, István Tomon 

Publication date: 8 August 2019

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.

Mathematics Subject Classification ID

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

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)