# Discrepancy of random bipartite graphs

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?

• can we just take k=1? May 26 at 16:46
• @Antoine Labelle As I wrote in a comment after James Martin's answer, it is frowned upon to change questions after they are answered. (Otherwise, people might not spend time answering your questions.) You can just ask a new question. Edits should be used to clarify questions, not to change them. May 26 at 23:19
• Sorry about that. I posted the modified question here : mathoverflow.net/q/423392/160416. May 26 at 23:50

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$$.
• Thanks, I didn't thought about that. In this case I guess that the question I really want to ask is: for a fixed $\epsilon$, does there exist $K(\epsilon)$ such that for $k>K(\epsilon)$ the discrepancy is $<\epsilon$ almost surely as $n \to \infty$. May 26 at 20:46