Threshold functions for the bipartite Turán property

Anant P. Godbole ; Ben Lamorte ; Erik Jonathan Sandquist

The electronic journal of combinatorics, Tome 4 (1997) no. 1

Résumé

Let $G_2(n)$ denote a bipartite graph with $n$ vertices in each color class, and let $z(n,t)$ be the bipartite Turán number, representing the maximum possible number of edges in $G_2(n)$ if it does not contain a copy of the complete bipartite subgraph $K(t,t)$. It is then clear that $\zeta(n,t)=n^2-z(n,t)$ denotes the minimum number of zeros in an $n\times n$ zero-one matrix that does not contain a $t\times t$ submatrix consisting of all ones. We are interested in the behaviour of $z(n,t)$ when both $t$ and $n$ go to infinity. The case $2\le t\ll n^{1/5}$ has been treated elsewhere; here we use a different method to consider the overlapping case $\log n\ll t\ll n^{1/3}$. Fill an $n \times n$ matrix randomly with $z$ ones and $\zeta=n^2-z$ zeros. Then, we prove that the asymptotic probability that there are no $t \times t$ submatrices with all ones is zero or one, according as $z\ge(t/ne)^{2/t}\exp\{a_n/t^2\}$ or $z\le(t/ne)^{2/t}\exp\{(\log t-b_n)/t^2\}$, where $a_n$ tends to infinity at a specified rate, and $b_n\to\infty$ is arbitrary. The proof employs the extended Janson exponential inequalities.

Détail

DOI : 10.37236/1303

Classification : 05C50, 05C80, 05C35, 05B30
Mots-clés : Turán number, zero-one matrix