This is a crosspost from MathStackExchange (original question).
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?
Best Answer
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$.