This is a crosspost from MathStackExchange ([original question](https://math.stackexchange.com/q/4454178/789954)).


Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a random bipartite graph 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 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$.



> 
> Is it true that, for every $\epsilon>0$, as $n \to \infty$ the probability that the discrepancy is greater than $\epsilon$ goes to zero?
> 
> 
> 


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|>\epsilon\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
$$\sum\_{A,B} \mathbb{P}\left(\left|\frac{E(A,B)}{kn}-\frac{|A||B|}{n^2}\right|>\epsilon\right) \to \infty$$
(see the MSE post for details on that).


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$. Is it true that, for every $\epsilon>0$, as $n \to \infty$ the probability that the discrepancy is greater than $\epsilon$ go to zero in the hypergraph case?



Discrepancy of random bipartite graphs
The expected degree of a vertex is $k$, which we are keeping fixed as $n\to\infty$. As $n\to\infty$, the vertex degree distribution converges to Poisson($k$). In particular, a proportion roughly $e^{-k}$ of the vertices have degree $0$.


Let $A$ be the set of vertices in $X$ which have degree $0$. Let $B$ be the whole of $Y$. Then $\frac{E(A,B)}{kn}=0$, while $\frac{|A||B|}{n^2}$ is typically close to $e^{-k}$. So for example, the probability that the discrepancy is greater than $e^{-k}/2$ goes to $1$ as $n\to\infty$.


