[proofplan] We use the probabilistic deletion method. Sample a binomial random bipartite graph $G \sim G(n, n, p)$ with edge probability $p = n^{-2/(t+1)}$, then delete one edge from every $K_{t,t}$ subgraph to obtain $\tilde{G}$. Linearity of expectation gives $\mathbb{E}[e(G)] = pn^2$, and a direct moment calculation with the choice $p = n^{-2/(t+1)}$ yields $\mathbb{E}[\#K_{t,t}(G)] \leq \tfrac{1}{4}n^{2-2/(t+1)}$. Subtracting, $\mathbb{E}[e(\tilde{G})] \geq \tfrac{3}{4}n^{2-2/(t+1)}$, so some realisation of $\tilde{G}$ achieves at least this many edges while containing no $K_{t,t}$, giving the required lower bound on $Z(n,t)$. [/proofplan] [step:Set up the random bipartite graph model and target parameters] Fix $t \geq 2$ and $n \geq 1$. Let $X = \{x_1, \ldots, x_n\}$ and $Y = \{y_1, \ldots, y_n\}$ be disjoint vertex sets of size $n$. Let \begin{align*} p := n^{-2/(t+1)} \in (0, 1]. \end{align*} Define a random bipartite graph $G = (X \sqcup Y, E)$ on $(\Omega, \mathcal{F}, \mathbb{P})$ by including each potential edge $x_i y_j$ (with $i, j \in \{1, \ldots, n\}$) independently with probability $p$. The edge indicators \begin{align*} \mathbb{1}_{\{x_i y_j \in E(G)\}} : \Omega &\to \{0, 1\} \end{align*} are therefore i.i.d. Bernoulli($p$), so $e(G) = \sum_{i,j} \mathbb{1}_{\{x_i y_j \in E(G)\}}$ and \begin{align*} \mathbb{E}[e(G)] = n^2 p = n^2 \cdot n^{-2/(t+1)} = n^{2 - 2/(t+1)}. \end{align*} [guided] The strategy is *probabilistic deletion*: we first produce a random graph $G$ that has many edges but may contain copies of $K_{t,t}$, then destroy every $K_{t,t}$ by deleting a single edge from each. Provided the expected number of $K_{t,t}$ subgraphs is small compared to $\mathbb{E}[e(G)]$, the deletion costs few edges and we end up with a $K_{t,t}$-free graph that still has many. We pick the edge probability $p$ to balance the two expectations. The key tension: large $p$ gives more edges but also more $K_{t,t}$'s; small $p$ gives fewer $K_{t,t}$'s but fewer edges. The value $p = n^{-2/(t+1)}$ is the sweet spot — we will see in the next step that it makes $\mathbb{E}[\#K_{t,t}(G)]$ a constant fraction of $\mathbb{E}[e(G)]$, leaving a positive residual after deletion. Formally, we work on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ carrying the independent Bernoulli($p$) edge indicators $\mathbb{1}_{\{x_i y_j \in E(G)\}}$ for $(i, j) \in \{1, \ldots, n\}^2$. Linearity of expectation then gives the edge-count expectation directly: \begin{align*} \mathbb{E}[e(G)] = \sum_{i=1}^n \sum_{j=1}^n \mathbb{E}[\mathbb{1}_{\{x_i y_j \in E(G)\}}] = n^2 p = n^{2 - 2/(t+1)}. \end{align*} [/guided] [/step] [step:Bound the expected number of $K_{t,t}$ subgraphs] Let $Z$ count the unordered pairs $(A, B)$ with $A \subseteq X$, $B \subseteq Y$, $|A| = |B| = t$, and $G[A \cup B] \supseteq K_{t,t}$ (i.e., every edge between $A$ and $B$ is present in $G$): \begin{align*} Z := \sum_{\substack{A \subseteq X, |A| = t \\ B \subseteq Y, |B| = t}} \mathbb{1}_{\{K_{A,B} \subseteq G\}}. \end{align*} Each indicator is a product of $t^2$ independent Bernoulli($p$) indicators, so $\mathbb{E}[\mathbb{1}_{\{K_{A,B} \subseteq G\}}] = p^{t^2}$. By [linearity of expectation](/theorems/???), \begin{align*} \mathbb{E}[Z] = \binom{n}{t}^2 p^{t^2}. \end{align*} Using the standard bound $\binom{n}{t} \leq n^t / t! \leq n^t / 2$ (valid for $t \geq 2$), we have $\binom{n}{t}^2 \leq n^{2t}/4$, so \begin{align*} \mathbb{E}[Z] \leq \frac{n^{2t} p^{t^2}}{4}. \end{align*} We compute $n^{2t} p^{t^2}$ with $p = n^{-2/(t+1)}$ in exponent form. Factoring as $(n^2 p^t)^t$, \begin{align*} n^2 p^t = n^2 \cdot n^{-2t/(t+1)} = n^{2 - 2t/(t+1)} = n^{(2(t+1) - 2t)/(t+1)} = n^{2/(t+1)}, \end{align*} so $n^{2t} p^{t^2} = (n^2 p^t)^t = n^{2t/(t+1)} = n^{2 - 2/(t+1)}$. Substituting, \begin{align*} \mathbb{E}[Z] \leq \frac{1}{4} n^{2 - 2/(t+1)}. \end{align*} [guided] We define the random variable $Z$ counting the number of complete bipartite subgraphs $K_{t,t}$ in $G$. Each such subgraph is determined by a choice of $t$ vertices $A \subseteq X$ and $t$ vertices $B \subseteq Y$; we say $K_{A,B} \subseteq G$ when all $t^2$ possible edges between $A$ and $B$ are present in $G$. There are $\binom{n}{t}^2$ such pairs $(A, B)$, and for a fixed pair the event $\{K_{A,B} \subseteq G\}$ is the intersection of $t^2$ independent Bernoulli($p$) events (one per potential edge), so its probability is $p^{t^2}$. Linearity of expectation — which requires no independence between the indicators — gives \begin{align*} \mathbb{E}[Z] = \sum_{(A, B)} \mathbb{P}(K_{A,B} \subseteq G) = \binom{n}{t}^2 p^{t^2}. \end{align*} We now estimate this in closed form. The bound $\binom{n}{t} \leq n^t / t!$ is standard; for $t \geq 2$ we have $t! \geq 2$, so $\binom{n}{t}^2 \leq n^{2t}/4$. Thus \begin{align*} \mathbb{E}[Z] \leq \frac{1}{4} n^{2t} p^{t^2}. \end{align*} The product $n^{2t} p^{t^2}$ looks formidable but simplifies cleanly. The trick is to factor it as $(n^2 p^t)^t$: we have $n^{2t} = (n^2)^t$ and $p^{t^2} = (p^t)^t$, so \begin{align*} n^{2t} p^{t^2} = (n^2 p^t)^t. \end{align*} With $p = n^{-2/(t+1)}$, \begin{align*} n^2 p^t = n^2 \cdot n^{-2t/(t+1)} = n^{2 - 2t/(t+1)}. \end{align*} Simplifying the exponent: $2 - \tfrac{2t}{t+1} = \tfrac{2(t+1) - 2t}{t+1} = \tfrac{2}{t+1}$. So $n^2 p^t = n^{2/(t+1)}$, and hence \begin{align*} n^{2t} p^{t^2} = \left(n^{2/(t+1)}\right)^t = n^{2t/(t+1)} = n^{2 - 2/(t+1)}. \end{align*} Substituting, \begin{align*} \mathbb{E}[Z] \leq \frac{1}{4} n^{2 - 2/(t+1)}. \end{align*} The miraculous coincidence — that $\mathbb{E}[Z]$ and $\mathbb{E}[e(G)]$ have the same $n$-exponent $2 - 2/(t+1)$ — is precisely the reason we chose $p = n^{-2/(t+1)}$. This alignment is what makes the deletion argument yield a non-trivial edge count. [/guided] [/step] [step:Delete one edge per $K_{t,t}$ to obtain a $K_{t,t}$-free graph] Define a measurable procedure: for each realisation $G(\omega)$, fix an arbitrary total ordering on the set of pairs $(A, B)$ with $A \subseteq X$, $B \subseteq Y$, $|A| = |B| = t$, and $K_{A, B} \subseteq G(\omega)$; then for each such pair (in order) delete from $G(\omega)$ one distinguished edge of $K_{A,B}$, unless it has already been deleted by a previous pair. Let $\tilde{G}(\omega)$ denote the resulting graph. By construction $\tilde{G}$ contains no $K_{t,t}$: any would-be copy $K_{A',B'} \subseteq \tilde{G}$ would also have been a copy in $G$, hence would have had its distinguished edge removed. The total number of edge deletions is at most $Z$, since each $K_{t,t}$-copy removes at most one edge, so \begin{align*} e(\tilde{G}) \geq e(G) - Z. \end{align*} Taking expectations and using the bounds from the previous two steps, \begin{align*} \mathbb{E}[e(\tilde{G})] \geq \mathbb{E}[e(G)] - \mathbb{E}[Z] \geq n^{2-2/(t+1)} - \frac{1}{4}n^{2-2/(t+1)} = \frac{3}{4} n^{2-2/(t+1)}. \end{align*} In particular $\mathbb{E}[e(\tilde{G})] \geq \tfrac{1}{2} n^{2-2/(t+1)}$. [guided] We now execute the deletion. The goal is to turn the random graph $G$ — which has many edges in expectation but may contain $K_{t,t}$'s — into a $K_{t,t}$-free graph $\tilde{G}$ while losing as few edges as possible. The deletion procedure: enumerate the $K_{t,t}$-copies in $G(\omega)$ (using any fixed total ordering on subset pairs $(A, B)$, to make the procedure deterministic as a function of $\omega$), and for each copy remove one distinguished edge — say, the lexicographically least edge of $K_{A,B}$. If that edge has already been deleted by an earlier copy, we do nothing. Two observations: - *$\tilde{G}$ is $K_{t,t}$-free.* Suppose $K_{A',B'}$ were a subgraph of $\tilde{G}$. Since $\tilde{G}$ is obtained from $G$ by deleting edges, we would also have $K_{A',B'} \subseteq G$. But then $(A', B')$ was processed during the deletion and its distinguished edge was removed — contradiction. - *Edge loss is bounded by $Z$.* Each $K_{t,t}$-copy deletes at most one edge (possibly zero, if its distinguished edge was already deleted), so the number of deleted edges is at most $Z$. Hence pointwise (in $\omega$): \begin{align*} e(\tilde{G}) \geq e(G) - Z. \end{align*} Taking expectations — which we may do by [linearity of expectation](/theorems/???) — and plugging in the bounds from the previous two steps, \begin{align*} \mathbb{E}[e(\tilde{G})] \geq \mathbb{E}[e(G)] - \mathbb{E}[Z] \geq n^{2-2/(t+1)} - \tfrac{1}{4} n^{2-2/(t+1)} = \tfrac{3}{4} n^{2-2/(t+1)}. \end{align*} We keep the weaker lower bound $\mathbb{E}[e(\tilde{G})] \geq \tfrac{1}{2} n^{2-2/(t+1)}$ stated in the theorem, though $\tfrac{3}{4}$ is immediate. [/guided] [/step] [step:Extract a deterministic $K_{t,t}$-free graph and conclude] Since $\mathbb{E}[e(\tilde{G})] \geq \tfrac{1}{2} n^{2-2/(t+1)}$, there exists at least one outcome $\omega^* \in \Omega$ with \begin{align*} e(\tilde{G}(\omega^*)) \geq \tfrac{1}{2} n^{2-2/(t+1)}, \end{align*} for otherwise every realisation would have $e(\tilde{G}(\omega)) < \tfrac{1}{2} n^{2-2/(t+1)}$ and the expectation would strictly contradict the bound. The graph $\tilde{G}(\omega^*)$ is a concrete bipartite graph on $2n$ vertices, contains no $K_{t,t}$ by Step 3, and has at least $\tfrac{1}{2} n^{2 - 2/(t+1)}$ edges. By definition $Z(n, t)$ is the maximum number of edges in a $K_{t,t}$-free bipartite graph on $(n, n)$ vertices, so \begin{align*} Z(n, t) \geq e(\tilde{G}(\omega^*)) \geq \tfrac{1}{2} n^{2 - 2/(t+1)}. \end{align*} This is the required lower bound. [/step]