Discrepancy of random bipartite graphs (2)

Question

This question is a modification of the one asked here, which turned out to ask for something too strong to be true.

Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ and define a random bipartite graph $G(k,n)$ on $X \sqcup Y$ in an Erdos-Renyi fashion by putting an edge between each pair $x, y$ with $x\in X$, $y\in Y$ with probability $\frac{k}{n}$. Define the discrepancy $\text{Disc}(G)$ of the resulting bipartite graph as the maximum of $$\left|\frac{E(A,B)}{kn}-\frac{|A||B|}{n^2}\right|$$ over all the subsets $A \subset X$, $B\subset Y$, where $E(A, B)$ is the number of edges between vertices in $A$ and vertices in $B$.

Given $\varepsilon>0$, does there exist $K(\varepsilon)>0$ such that, for every $k>K(\varepsilon)$, the probability that $\text{Disc}(G(k,n))>\varepsilon$ goes to zero as $n \to \infty$.

In other words, do all pairs of subsets have roughly the expected number of edges between them with high probability? Note that the naive approach of bounding $\mathbb{P}\left(\left|\frac{E(A,B)}{kn}-\frac{|A||B|}{n^2}\right|>\varepsilon\right)$ independently for each pair $A,B$ and then use the union bound on all possible pairs $A, B$ cannot work, since one can prove that, for any fixed $k, \varepsilon$, $$\sum_{A,B} \mathbb{P}\left(\left|\frac{E(A,B)}{kn}-\frac{|A||B|}{n^2}\right|>\epsilon\right) \to \infty.$$ Moreover, the constant $K(\varepsilon)$ is important since, as shown by James Martin in the previous version of that question, the statement is false if $k$ is too small with respect to $\varepsilon$.

In case the statement is true, I'm also interested in the natural generalization to $r$-partite $r$-uniform hypergraphs. That is, fix vertex sets $X_1, \ldots, X_r$ and put an edge between $x_1, \ldots, x_r$ for each $x_1 \in X_1, \ldots x_r\in X_r$ with probability $\frac{k}{n^{r-1}}$. Define the discrepancy as the maximum of $$\left|\frac{E(A_1,\ldots, A_r)}{kn}-\frac{|A_1|\cdots|A_r|}{n^r}\right|$$ over all the $r$-tuples of subsets $(A_i \subset X_i)$, where $E(A_1, \ldots, A_r)$ is the number of edges between $A_1, \ldots, A_r$. Given $\varepsilon>0$, does there exist $K_r(\varepsilon)>0$ such that, for every $k>K_r(\varepsilon)$, the probability that the discrepancy is greater than $\varepsilon$ goes to zero as $n \to \infty$?

Answer 1

The answer is yes, and the union bound actually does work. By applying the multiplicative Chernoff bound found here with $\delta=\frac{\varepsilon n^r}{N}$ and $\mu=\frac{kN}{n^{r-1}}$ where $N=|A_1|\cdots|A_r|$ we find that $$\mathbb{P}\left(\left|\frac{E(A_1,\ldots, A_r)}{kn}-\frac{|A_1|\cdots|A_r|}{n^r}\right|>\varepsilon\right)\le 2\exp\left(-\frac{\delta^2\mu}{2+\delta}\right)$$ $$=2\exp\left(-\frac{\varepsilon^2 k n^{r+1}}{2N+\varepsilon n^r}\right)$$ $$\le 2\exp\left(-\frac{\varepsilon^2 k n}{2+\varepsilon}\right)$$ Therefore if $\frac{\varepsilon^2 k}{2+\varepsilon}>r\log 2$, the discrepancy is at most $\varepsilon$ almost surely as $n\to \infty$.