# Discrepancy of random bipartite graphs (2)

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$$?

• Why is union bound so bad? On the first glance, the guy $E(A,B)-k|A|\cdot |B|/n$ behaves as normal with variance $kn$, so the probability of the deviation of order $kn$ is exponential in $kn$ that should be enough. Commented May 27, 2022 at 10:49
• I think you're right, I got confused. The union bound couldn't work for the first version of the question because of factors of $\varepsilon$, but I think it might work here, thought I have to think that through. Commented May 27, 2022 at 12:18

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$$.