Threshold Functions for the Bipartite Turán Property

Anant P. Godbole

Department of Mathematical Sciences, Michigan Technological University, Houghton, MI 49931-1295,

U.S.A. (anant@mtu.edu)

Ben Lamorte

Engineering and Economic Systems Department, Stanford University, Stanford, CA 93405-4025, U.S.A.

(lamorte@leland.stanford.edu)

Erik Jonathan Sandquist

Department of Mathematics, Cornell University, Ithaca, NY 14853-7901, U.S.A. (ejs9@cornell.edu)

Submitted: May 20, 1997; Accepted: August 20, 1997 MR Subject Numbers: 05C50, 05C80, 05C35, 05B30

ABSTRACT

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 ζ(n, t) = n^{2} − z(n, t) denotes the minimum number of zeros in an n × n zero-one matrix that does not contain a t × 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 ≤ t ≪ n^{1/5} has been treated in [9]; here we use a different method to consider the overlapping case log n ≪ t ≪ n^{1/3}. Fill an n × n matrix randomly with z ones and ζ = n^{2} − z zeros. Then, we prove that the asymptotic probability that there are no t × t submatrices with all ones is zero or one, according as z ≥ (t/ne)^{2/t} exp{a_{n}/t^{2}} or z ≤ (t/ne)^{2/t} exp{(log t − b_{n})/t^{2}}, where a_{n} tends to infinity at a specified rate, and b_{n} → ∞ is arbitrary. The proof employs the extended Janson exponential inequalities [1].

1. INTRODUCTION AND STATEMENT OF RESULTS

Given a graph F, what is the maximum number of edges in a graph on n vertices that does not contain F as a subgraph? In the bipartite case, we let z(n, t) denote the (diagonal) bipartite Turán number, which represents the maximum number of edges in a bipartite graph [with n vertices in each color class] that does not contain a complete bipartite graph K(t, t) of order t. An equivalent formulation of this problem is in terms of zero-one matrices, and is called the problem of Zarankiewicz: What is the smallest number of zeros ζ(n, t) that can be strategically placed among the entries of an n × n zero-one matrix so as to prevent the existence of a t × t submatrix of all ones? We remind the reader that, in this formulation, the submatrix in question need not have consecutive rows or columns. It is clear that ζ(n, t) = n^{2} − z(n, t). [Generalizing this problem to s × t submatrices of a zero-one matrix of order m×n leads naturally to the numbers z(m, n, s, t) and ζ(m, n, s, t); Bollobás [4] has shown that

2ex(n, K(s, t)) ≤ z(n, n, s, t),

where ex(n, F) denotes the maximum number of edges in a graph on n vertices that does not contain F as a subgraph.] In contrast with the classical Turán numbers, definitive general results are not known in the bipartite case. The initial search for numerical values of z(n, t), t = 3, 4, 5 …; n = 4, 5, 6, …, due to Zarankiewicz; Sierpinski; Brzezinski; Čulik; Guy; and Znám, is chronicled in [4], as is the history of research (due to Hartman, Mycielski and Ryll-Nardzewski; and Rieman) leading to asymptotic bounds on z(n, 2), and on z(m, n, s, t) (the latter set of results are due to Kövári, Sós and Turán; Hyltén-Cavallius; and Znám). The asymptotics of the numbers z(n, n, 2, t) (t fixed) and z(n, 3) have most recently been investigated by Füredi ([6],[7]) who also describes the early related work of Rieman; Kövári, Sós and Turán; Erdős, Rényi and Sós; Brown; Hyltén-Cavallius; and Mörs. An excellent survey of these and related questions can be found in Section VI.2 of [4]. A problem similar in spirit to the Zarankiewicz question is the object of intense study in reliability theory; see [2] for details and references, and [3] for background on the Stein-Chen method of Poisson approximation.

the electronic journal of combinatorics 4 (1997), #R18 3

Most of the work described in the previous two paragraphs has focused on the case where the dimensions (s, t) of the forbidden submatrix are fixed, and n tends to infinity; a notable exception to this is provided by the recent work of Griggs and Ouyang [11], and Gentry [8], who each study the half-half case, and derive several bounds and exact values for the numbers z(2m, 2n, m, n). We continue this trend in this paper, focus on the diagonal case m = n; s = t, and study the asymptotics of the problem as both n and t tend to infinity. Our arguments will force us to assume that log n ≪ t ≪ n^{1/3}, where, given two non-negative sequences a_{n} and b_{n}, we write a_{n} ≪ b_{n} if a_{n}/b_{n} → 0 (n → ∞). We thus obtain an extension of the results in [9], where the overlapping case 2 ≤ t ≪ n^{1/5} was considered. Similarities and differences between the approaches in [9] and the present paper will be given later in this section, and in the next section. Since z(n, t) ∼ n^{2} for the range of t’s that we consider, we will occasionally rephrase our results in terms of the minimum number ζ(n, t) of zeros of an n × n 0-1 matrix that prevents the existence of a t × t submatrix of all ones. The key general bounds due to Znám [15] and Bollobás [4] (Theorems VI.2.5 and VI.2.10 in [4], adapted to our purpose,) are as follows:

(n^{2} − (t − 1)^{1/t}n^{2− \frac{1}{t}} − \frac{n(t − 1)}{2}) ≤ ζ(n, t) ≤ \frac{2n^{2} log n}{t}\{1 + o(1)\} (t → ∞; t ≫ log n),

(1)

In particular, with t = n^{α}, α < 1/2, we have

(1 − α)n^{2−α} log n{1 + o^{∗}(1)} ≤ ζ(n, n^{α}) ≤ 2n^{2−α} log n{1 + o(1)}.  (2)

We restate (1) and (2) in probabilistic terms as follows: Consider the probability measure P_{u,z} that randomly and uniformly places ζ zeros and z = n^{2} − ζ ones among the entries of the n × n matrix [the subscript u refers to the fact that the allotment is \underline{u}niform, and the subscript z to the fact that there are z ones in the array.] Let X denote the random variable that equals the number of t × t submatrices consisting of all ones [we often denote such a t × t matrix by J_{t}]. In other words,

X = \begin{matrix}\binom{n}{t} & ^{2} \\ ∑ \\ j=1 \end{matrix} I_{j}

where I_{j} = 1 if the j^{th} t × t submatrix equals J_{t} [I_{j} = 0 otherwise]. Equation (1) may then be rephrased as

ζ ≤ n^{2} − (t − 1)^{1/t}n^{2− \frac{1}{t}} − \frac{n(t − 1)}{2} ⇒ P_{u,z}(X = 0) = 0  (3)

and

ζ ≥ \frac{2n^{2} log n}{t}\{1 + o(1)\} ⇒ P_{u,z}(X = 0) > 0.  (4)

The rate of growth of the numbers ζ(n, t) is given by (3) and (4); if t = n^{α}, for example, this rate is of order n^{2−α} log n. We will primarily be concerned with proving results that maintain the flavor of Bollobás’ and Znám’s results, through the establishment of a threshold phenomenon for P_{u,z}(X = 0), i.e., a threshold function for the bipartite Turán property.

One may obtain a clue as to the direction in which results such as (3) and (4) may be steered by using the following rather elementary probabilistic argument: Suppose that P denotes the probability measure that independently allots, to each position in [n] × [n], a one with probability p and a zero with probability q = 1 − p, where p and q are to be determined. Then, with X representing the same r.v. as before, E(X) = \binom{n}{t}^{2}p^{t^{2}} ≤ K(ne/t)^{2t}p^{t^{2}}/t → 0 if p = (t/ne)^{2/t} exp{(log t − b_{n})/t^{2}}, where b_{n} → ∞ is arbitrary, so that by Markov’s inequality, P(X = 0) → 1 if the expected number of ones is less than n^{2}(t/ne)^{2/t} exp{(log t − b_{n})/t^{2}}. The question, of course, is whether this is true if the actual number of ones is at the same level, i.e., under the measure P_{u,z}.

In this paper, we use the extended Janson exponential inequalities [1] to show that both P(X = 0) and P_{u,z}(X = 0) enjoy a sharp threshold at the level suggested by the above reasoning. Specifically, we prove

Theorem. Consider the probability measure P that independently allots, to each position in X = [n] × [n] = {1, 2, …, n} × {1, 2, …, n}, a one with probability p and a zero with probability q = 1 − p. Let t satisfy log n ≪ t = o(n^{1/3}), and set X = ∑\binom{n}{t}^{2}_{j=1} I_{j}, with I_{j} = 1 iff J = J_{t}, where J represents the j^{th} t × t submatrix of X, and I_{j} = 0 otherwise. Then

p = (\frac{t}{ne})^{2/t} exp \{\frac{log t + a_{n}}{t^{2}} \} ⇒ P(X = 0) → 0 (n → ∞)

the electronic journal of combinatorics 4 (1997), #R18 5

and

p = (\frac{t}{ne})^{2/t} exp \{\frac{log t − b_{n}}{t^{2}} \} ⇒ P(X = 0) → 1 (n → ∞)

where b_{n} → ∞ is arbitrary, and a_{n} ≥ 2t + log(n^{2}/t^{2}) + δ_{n}, where δ_{n} → ∞ is arbitrary.

As a consequence of the above theorem, we will show that it is possible to prove a result with a fixed (as opposed to random) number of ones, i.e., to prove that P_{u,z}(X = 0) tends to zero or one according as z, the number of ones in the matrix, is larger than n^{2}(t/ne)^{2/t} exp{(log t + a_{n})/t^{2}}, or smaller than n^{2}(t/ne)^{2/t} exp{(log t − b_{n})/t^{2}}. This comes as no surprise, since it is well-known that many graph theoretical properties hold under the model G(n, p) if and only if they hold under the model G(n, m), with m = np. In particular, with t = n^{α}, we see that J_{t} submatrices pass from being sparse objects to abundant ones at the level ζ = 2(1 − α)n^{2−α} log n. As a further corollary, we will be able to improve the general upper bound ζ(n, t) ≤ (2n^{2} log n)/t{1 + o(1)} to ζ(n, t) ≤ 2n^{2}(log(n/t))/t{1 + o(1)}, with the most significant improvement being when t = n^{α}.

The versatility of Janson’s inequalities in combinatorial situations has been welldocumented; see, for example, the wide range of examples in Chapter 8 of [1], or the work of Janson, Łuczak, and Ruciński [12], who establish the definitive threshold results for Turán-type properties in the unipartite case. Recent applications of these exponential inequalities include an an analysis of the threshold behaviour of random covering designs ([10]); of random Sidon sequences ([14]); and of the Schur property of random subsets ([13]). A recent analysis of graph-theoretic properties with sharp thresholds may be found in [5].

We end this section by stating the connections between this paper and [9]. In [9], the same problem was treated as in this paper, and the (regular) Janson exponential inequalities yielded the threshold function for the Zarankiewicz property for 2 ≤ t ≪ n^{1/5}. A comment was made that the same technique would probably work, with a large amount of extra effort, for t’s up to o(n^{1/3}). In this paper, we choose, instead, to use the extended Janson inequalities, together with a different technique for bounding the covariance terms, to prove this fact. We indicate methods by which the main result could, possibly, be extended to t = o(n^{1/2}). Other points of difference and similarity with [9] will be indicated at various points throughout this paper.

the electronic journal of combinatorics 4 (1997), #R18 6

2. PROOFS

Proof of the Theorem:

We have already provided a proof of the second part of the theorem using nothing more than Markov’s inequality, and now turn to the first half. Throughout, we assume that p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}}, with conditions on a_{n} to be determined. Let B_{j} be the event that the j^{th} t × t submatrix, denoted by J, equals J_{t}, i.e., has all ones. We recall the Janson and extended Janson inequalities ([1]):

P(X = 0) ≤ exp \{−μ + \frac{Δ}{2(1 − ε)}\};  (5)

and

P(X = 0) ≤ exp \{−\frac{μ^{2}(1 − ε)}{2Δ}\} ,  (6)

where

ε =p^{t^{2}};
μ =\binom{n}{t}^{2}p^{t^{2}} = E(X); and
Δ =μ ∑_{{r,c=1 \atop r+c<2t}}^{t} \binom{t}{r}\binom{n − t}{t − r}\binom{t}{c}\binom{n − t}{t − c}p^{t^{2}−rc};  (7)

and (in (6)) provided that Δ ≥ μ(1−ε). We also mention the bound based on Chebychev’s inequality, known in the combinatorics literature ([1]) as the second-moment bound:

P(X = 0) ≤ \frac{Δ + μ}{μ^{2}}.  (8)

In [9], (5) was used to obtain the required threshold for 2 ≤ t ≪ n^{1/5} with Δ as in (7), and it was noted that the second moment bound (8) could also be employed–but with a worse rate of approximation, and without any significant reduction in the calculation. It can readily be checked, moreover, that if the exact form of (7) is used for Δ, then Δ = o(1) iff μ^{2}/Δ → ∞ iff t = o(n^{1/5}), so that even the extended Janson inequality will not lead to an improvement in the results of [9]. We need, therefore, to work with a different method in conjunction with (6), and proceed as follows: Since k! ≥ A\sqrt{k}(k/e)^{k}, k = 1, 2, …, and

the electronic journal of combinatorics 4 (1997), #R18 7

k! ≥ (k/e)^{k}, k = 0, 1, 2, …, where A = e/\sqrt{2} and we interpret 0^{0} as unity, (7) yields the estimate

Δ ≤ Δ_{1} + Δ_{2}  (9)

where

Δ_{1} ≤\frac{4}{e^{4}} \binom{n}{t}^{2}p^{2t^{2}} ∑_{r,c=1}^{t−1} (\frac{te}{c})^{c} (\frac{te}{r})^{r} (\frac{ne}{t − r} )^{t−r} (\frac{ne}{t − c})^{t−c} \frac{1}{\sqrt{rc(t − r)(t − c)}}p^{−rc}
≤\binom{n}{t}^{2}p^{2t^{2}} ∑_{r,c=1}^{t−1} (\frac{te}{c})^{c} (\frac{te}{r})^{r} (\frac{ne}{t − r} )^{t−r} (\frac{ne}{t − c})^{t−c} \frac{1}{t − 1}p^{−rc}
=\binom{n}{t}^{2}p^{2t^{2}} ∑_{r,c=1}^{t−1} φ(r, c) say,  (10)

and

Δ_{2} ≤ \binom{n}{t}^{2}p^{2t^{2}} ∑_{{max\{r,c\}=t \atop r+c<2t}} ψ(r, c),  (11)

where

ψ(r, c) = (t − 1)φ(r, c) = \{ \begin{matrix}(\frac{te}{c})^{c} (\frac{te}{r})^{r} (\frac{ne}{t−r} )^{t−r} (\frac{ne}{t−c})^{t−c} p^{−rc} & (max\{r, c\} < t); \\ e^{t} (\frac{te}{r})^{r} (\frac{ne}{t−r} )^{t−r} p^{−rt} & (c = t, r < t); \\ e^{t} (\frac{te}{c})^{c} (\frac{ne}{t−c})^{t−c} p^{−ct} & (r = t, c < t) \\ e^{2t}p^{−t^{2}} & (r = c = t). \end{matrix}

Note that φ and ψ are each defined on the compact subset [1, t]^{2} of R^{2}. Now, in the main result of [9], both a_{n} and b_{n} could be taken to be arbitrary. We cannot prove such a result, in our current theorem, for t’s of the form Ω(n^{1/5}) ≤ t = o(n^{1/3}) due, basically, to the above-described “inflation” in the value of Δ. Actually, as we shall see, this is not really an inflation at all: when p equals a slightly higher value, the proof of the theorem will reveal that the maximum summand in Δ (given by (9) through (11)) corresponds to (1,1), whereas the maximum summand in [9] was at (t − 1, t), but for a smaller value of p, and with Δ given by (7). The overall effect, however, is for Δ to decrease. The proof of the theorem proceeds by a sequence of lemmas:

Lemma 1. The function ψ(r, c), extended to the closed domain A = [1, t]^{2} \ (t − 1, t]^{2} of R^{2}, has critical points only along the diagonal {(r, c) : r = c} Proof. Writing ψ on the interior of A as

ψ(r, c) = exp \{log A_{c} + r log (\frac{te}{r}) + (t − r) log (\frac{ne}{t − r} ) + rc log s\}

where A_{c} depends only on c, and s = 1/p, we see that

\frac{∂ψ}{∂r} = e^{log ψ} \{log (\frac{te}{r}) − log (\frac{ne}{t − r} ) + c log s\}

which equals zero if

\frac{(t − r)s^{c}}{r} = \frac{n}{t}.

Similarly we verify that ∂ψ/∂c = 0 if (t − c)s^{r}/c = n/t. It follows, that at a critical point,

\frac{(t − r)}{rs^{r}} = \frac{(t − c)}{cs^{c}}.

Now, since the function η(x) = (t − x)/xs^{x}; (1 ≤ x ≤ t), is decreasing, it follows that η(r) = η(c) ⇒ r = c. The lemma follows.

Lemma 2. ψ(1, 1) ≥ ψ(1, x) = ψ(x, 1) ∀x ∈ [1, t], provided that t^{2} = o(n) and t ≫ log n.

Proof. We show that ψ(1, x) is decreasing in x. Since ψ(1, x) = K(te/x)^{x}(ne/(t − x))^{t−x}p^{−x} for a constant K, we see that the sign of dψ(1, x)/dx is determined by the quantity log(te/x)−log(ne/(t−x))+log s = log(t(t−x)s/nx), which is negative if t^{2}s ≤ n. This concludes the proof of Lemma 2, since p ≈ 1 in all the cases we consider.

Lemma 3. ψ(1, 1) ≥ φ(1, 1) ≥ ψ(t, x) = ψ(x, t) ∀x ∈ [1, t − 1], provided that t^{2} = o(n), t ≫ log n, and p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}} with a_{n} restricted to a range to be specified below.

Proof. We consider the function ψ(t, x) = e^{t}(te/x)^{x}(ne/(t − x))^{t−x}p^{−tx}, the sign of whose derivative is determined by the quantity log(t(t − x)s^{t}/nx); it is easy to verify that ψ′(t, x) ≥ 0 provided that x ≤ t^{2}s^{t}/(n + ts^{t}). We next find conditions under which t^{2}s^{t}/(n + ts^{t}) ≥ t − 1; this inequality may be checked to hold provided that s^{t} ≥ n, i.e., if np^{t} ≤ 1. Now if we set p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}} we see that we must have

exp{(log t + a_{n})/t} ≤ ne^{2}/t^{2}  (12)

the electronic journal of combinatorics 4 (1997), #R18 9

in order for t^{2}s^{t}/(n + ts^{t}) to exceed t − 1. Since t^{2} = o(n), we can always choose a_{n} → ∞ slowly enough so that (12) holds. But we must be more careful, for reasons that will soon become apparent, and note, more specifically, that

a_{n} ≤ t log (\frac{ne^{2}}{t^{2}} ) − log t  (13)

will certainly suffice. Lemma 3 will follow if we can show that φ(1, 1) ≥ ψ(t, t − 1), i.e., that (n/t)^{2t−3} ≥ 4p^{−t^{2}+t}, and thus, with p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}}, that exp{a_{n} − 2t} ≥ Kn/t^{2}. The last condition clearly holds if

a_{n} ≥ 2t + log (\frac{n}{t^{2}} ) + δ_{n},  (14)

where δ_{n} → ∞ is arbitrarily small; since 2t + log(n/t^{2}) + δ_{n} ≤ t log(ne^{2}/t^{2}) − log t, (13) and (14) complete the proof of Lemma 3. Lemma 4.

φ(1, 1) ≥ max{ψ(t − 1, x) : t − 1 ≤ x ≤ t} under the same conditions as in Lemma 3. Proof. Similar to that of Lemma 3; it turns out that Lemma 4 holds if

a_{n} ≥ 2t + log (\frac{n^{2}}{t^{2}} ) + δ_{n},  (15)

for any δ_{n} → ∞. Lemma 5. ψ(1, 1) ≥ ψ(r, r), where (r, r) is any critical point of ψ, provided that t = o(n^{1/2}), and p = (t/ne)^{2/t} exp{(log t+a_{n})/t^{2}}, where a_{n} ≤ t log(ne^{2}/t^{2})−log t is arbitrary. Proof. We shall show that α(r) = log \sqrt{ψ(r, r)}, and hence β(r) = ψ(r, r), is first decreasing and then increasing as a function of r if a_{n} is as stated above. Lemma 5 will then follow from Lemma 4. We have α(r) = r log(te/r) + (t − r) log(ne/(t − r)) − (r^{2}/2) log p, so that α(·) is increasing whenever

\frac{t(t − r)}{nr} ≥ p^{r}.  (16)

Note that both sides of (16) represent decreasing functions of r, and, moreover, that the left side is convex. We next exhibit the fact that (16) does not hold when r = 1, but does when r = t − 1; it will then follow that (16) holds for each r ≥ r_{0}.

the electronic journal of combinatorics 4 (1997), #R18 10

With r = 1, (16) is satisfied only if t^{2}/n ≥ p, which is clearly untrue since t^{2} = o(n) and p ∼ 1. Let r = t − 1. (16) is then equivalent to the condition np^{t} ≤ 1, which may be checked to hold, as in the proof of Lemma 3, for any a_{n} ≤ t log(ne^{2}/t^{2}) − log t. This concludes the proof of Lemma 5.

We have proved thus far that the function ψ, and thus the function φ, [(r, c) ∈ {1, 2, …, t}^{2} \ (t, t)], both achieve a maximum at (1,1) provided that t does not grow too rapidly (or too slowly), and that p is large enough, but not too large. Continuing with the proof, we assume that p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}}, with a_{n} = 2t + log(n^{2}/t^{2}) + δ_{n}, i.e., equal to the value specified by (15). If we can establish that P(X = 0) → 0 with this value of p, then the same conclusion is certainly valid, by monotonicity, if p assumes any larger value. So far, our analysis has led (roughly) to the conditions log n ≪ t ≪ n^{1/2}; we now see how the “legal” use of Janson’s inequalities forces further restrictions on t – in particular, we will need to assume that log n ≪ t ≪ n^{1/3}. Returning to the extended Janson inequality, we must first find conditions under which Δ ≥ μ; this condition will ensure the validity of (6). Since, by (7), Δ ≥ K\binom{n}{t}^{2}p^{2t^{2}}t^{2}(ne/t)^{2t−2}(1/t) for some constant K, and μ = \binom{n}{t}^{2}p^{t^{2}}, we must have

Kp^{t^{2}} ≥ \frac{t^{2t−3}}{n^{2t−2}e^{2t−2}}

for Δ to exceed μ. Setting p = (t/ne)^{2/t} exp{(a_{n} + log t)/t^{2}}, we see that Δ ≥ μ if

K (\frac{t}{ne})^{2t} te^{a_{n}} ≥ \frac{t^{2t−3}}{n^{2t−2}e^{2t−2}} ,

i.e., if

Kt^{4}e^{a_{n}} ≥ n^{2}e^{2},

or, if

a_{n} ≥ log (\frac{n^{2}e^{2}}{t^{4}K} ) .

This may certainly be assumed to be true, and we next investigate whether we have μ^{2}/Δ → ∞ for p = (t/ne)^{2/t} exp{(a_{n} + log t)/t^{2}}; this will be the final step in the proof of the theorem. We have, by Lemmas 1 through 5,

\frac{μ^{2}}{Δ} ≥\frac{\binom{n}{t}^{4}p^{2t^{2}}}{t^{2}\binom{n}{t}^{2}p^{2t^{2}}φ(1, 1)}

=\frac{\binom{n}{t}^{2}p}{t^{2}(te)^{2}(\frac{ne}{t−1})^{2t−2}(t − 1)^{−1}}
⪰\frac{(n − t)^{2t}p}{t(t/e)^{2t}t^{2}(te)^{2}(\frac{ne}{t−1})^{2t−2}(t − 1)^{−1}}
⪰\frac{n^{2}}{t^{6}} → ∞

if t = o(n^{1/3}); in the last two lines of the above calculation, the notation f ⪰ g means that f ≥ Kg for some positive constant K. This proves the theorem; as in [9], the use of the second moment method would have led to a proof with the same degree of computation as above, but with a far worse approximation for P(X = 0). Remarks. Observe that the above proof actually shows, as in [1], pp. 40–41, that X ∼ E(X) with high probability. The condition t ≫ log n arises at several points in our proof and is crucial. In a similar vein, we point out that the condition t = o(n^{1/3}) arose at the very end of our proof, when the generalized Janson inequality was invoked. A more careful analysis, using the chain of inequalities Δ ≤ \binom{n}{t}^{2}p^{2t^{2}}[φ(1, 1) + t^{2}T_{2}]; Δ ≤ \binom{n}{t}^{2}p^{2t^{2}}[φ(1, 1) + T_{2} + t^{2}T_{3}]; etc., where T_{2}, T_{3} … represent the second, third,… largest summands in (10) and (11), would clearly lead to improvements. We conjecture, therefore, that the main result is true when t = o(n^{1/2}), and also that a_{n} can be chosen (like b_{n}) to tend to infinity at an arbitrarily slow rate. The latter fact is known to be true for t = o(n^{1/5}) (see [9] for a proof). Now if one seeks to maximize φ (with Δ as in (7)) for p = (t/ne)^{2/t} exp{(a_{n} + log t)/t^{2}}, where a_{n} → ∞ at an arbitrarily slow rate, then the maximum is achieved, for all t = o(n^{1/2}), at (t − 1, t) (see [9]). The problem, however, is that the Janson and extended Janson inequalities are both valid only for t = o(n^{1/5}) (as proved in [9]), whilst for a Δ inflated as in (10) and (11), the bound (5) is not useful, and, as we have seen, the extended Janson inequality unfortunately requires, for t = o(n^{1/3}), that a_{n} grow at a fast enough rate–with the maximum of φ occurring at (1,1). Graphs of φ(r, c), drawn using MAT HEMAT ICA\begin{matrix}c \\ ◯ \end{matrix}, show how very sensitive the location of the maximum value of φ is to small changes in the arguments. A new approach is, therefore, needed to resolve the above conjecture. We end with two corollaries: Corollary 1. Consider the probability measure P_{u,z} which uniformly places ζ zeros and z = n^{2} − ζ ones among the entries of the n × n matrix. Let t satisfy log n ≪ t = o(n^{1/3}) and set X = ∑\binom{n}{t}^{2}_{j=1} I_{j}, with I_{j} = 1 or I_{j} = 0 according as the j^{th} t × t submatrix consists of all ones (or not). Then for any b_{n} → ∞, and a_{n} as in the theorem,

z = n^{2} (\frac{t}{ne})^{2/t} exp \{\frac{log t + a_{n}}{t^{2}} \} ⇒ P_{u,z}(X = 0) → 0 (n → ∞)

and

z = n^{2} (\frac{t}{ne})^{2/t} exp \{\frac{log t − b_{n}}{t^{2}} \} ⇒ P_{u,z}(X = 0) → 1 (n → ∞)

Proof. We clearly have, for each z, P_{u,z}(X = 0) = P(X = 0|the n×n matrix has z ones). Set p = (t/ne)^{2/t} exp{(log t + a_{n})/t^{2}} and let z denote the corresponding number of ones. Then

P(X = 0|z = n^{2}p) ≤ P(X = 0|z ≤ n^{2}p) ≤ 3P(X = 0) → 0

by the theorem, where the last inequality above follows due to the observation that P(A|B) ≤ P(A)/P(B) and the fact that the central limit theorem [or the approximate and asymptotic equality of the mean and median of a binomial distribution] imply that P(z ≤ n^{2}p) ≥ 1/3. This proves the first half of the corollary. Conversely, with p = (t/ne)^{2/t} exp{(log t − b_{n})/t^{2}} the same reasoning implies that

P(X ≥ 1|z = n^{2}p) ≤ P(X ≥ 1|z ≥ n^{2}p) ≤ 3P(X ≥ 1) → 0,

again by the theorem. This completes the proof.

Corollary 2. ζ(n, t) ≤ (2n^{2}/t)(log(n/t)){1 + o(1)}.

Proof. By Corollary 1,

ζ(n, t) ≤n^{2} \{1 − (\frac{t}{ne})^{2/t} exp \{\frac{log t − b_{n}}{t^{2}} \}\}
=n^{2} \{1 − exp \{−\frac{2}{t} log (\frac{ne}{t}) + \frac{log t − b_{n}}{t^{2}} \}\}
≤n^{2} \{\frac{2}{t} log (\frac{n}{t}) + \frac{2}{t} − \frac{log t}{t^{2}} + \frac{b_{n}}{t^{2}} \}
=\frac{2n^{2}}{t} log \frac{n}{t}\{1 + o(1)\},

as asserted.

Acknowledgement

The research of all three authors was partially supported by NSF Grant DMS-9322460. They would like to thank Jerry Griggs and Jianxin Ouyang for introducing them to the Problem of Zarankiewicz.

References

[1] N. ALON AND J. SPENCER, “The Probabilistic Method,” John Wiley and Sons, Inc., New York, 1992.

[2] A. BARBOUR, O. CHRYSSAPHINOU, AND M. ROOS, Compound Poisson approximation in systems reliability, Naval Research Logistics 43 (1996), 251–264.

[3] A. BARBOUR, L. HOLST, AND S. JANSON, “Poisson Approximation,” Clarendon Press, Oxford, 1992.

[4] B. BOLLOBÁS, “Extremal Graph Theory,” Academic Press, London, 1978.

[5] E. FRIEDGUT AND G. KALAI, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc., to appear (1996).

[6] Z. FÜREDI, New asymptotics for bipartite Turán numbers, J. Combinatorial Theory, Series A 75 (1996), 141–144.

[7] Z. FÜREDI, An upper bound on Zarankiewicz’ problem, Comb. Prob. Computing 5 (1996), 29–33.

[8] C. GENTRY, On the half-half case of the problem of Zarankiewicz. In preparation (1996).

[9] A. GODBOLE AND H. GRAZIANO, Contributions to the problem of Zarankiewicz. Submitted to J. Graph Theory (1996).

[10] A. GODBOLE AND S. JANSON, Random covering designs, J. Combinatorial Theory, Series A 75 (1996), 85–98.

[11] J. GRIGGS AND J. OUYANG, (0,1)-matrices with no half-half submatrix of ones. To appear in European J. Comb.

[12] S. JANSON, T. ŁUCZAK, AND A. RUCIŃSKI, An exponential bound for the probability of non-existence of a specified subgraph in a random graph, in “ Proceedings of

the electronic journal of combinatorics 4 (1997), #R18 14

the 1987 Poznan Conference on Random Graphs,” John Wiley and Sons, Inc., New York, 1990.

[13] V. RÖDL AND A. RUCIŃSKI, Rado partition theorem for random subsets of integers. Preprint (1996).

[14] J. SPENCER AND P. TETALI, Sidon sequences with small gaps, in “Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications,” Vol. 72, Springer Verlag, New York, 1995.

[15] Š. ZNÁM, Two improvements of a result concerning a problem of K. Zarankiewicz, Colloq. Math 13 (1965), 255-258.