3
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ can we just take k=1? $\endgroup$ May 26 at 16:46
  • $\begingroup$ @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. $\endgroup$ May 26 at 23:19
  • $\begingroup$ Sorry about that. I posted the modified question here : mathoverflow.net/q/423392/160416. $\endgroup$ May 26 at 23:50

1 Answer 1

7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ May 26 at 20:46
  • 3
    $\begingroup$ @Antoine Labelle In that case you should accept James' answer, and ask a new question. Changing questions after they are answered is not productive, as it would discourage people from thinking about the given questions. $\endgroup$ May 26 at 23:15
  • $\begingroup$ Sure, I'll do that $\endgroup$ May 26 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.