Erdös and Rényi's "On Random Matrices"

Математика Оставить комментарий

For our weekly research class I had to prepare a presentation of "On random matrices" by Erdös and Rényi. Despite the title, it is essentially about bipartite graphs, proving that a random bipartite graph on 2n vertices (n vertices in each part) with n\log n + cn + o(n) edges has positive probability of containing a set of n independent edges as n grows infinitely.

The paper is written in an over-concise manner and relies heavily on tricky manipulation of binomial coefficients. I spent several days figuring out all the details, so I thought it would be nice to have the commentary online, should someone ever need help on the paper.

My first problem was the transformation of equation (1.7) into equation (1.9). The quantities S_i are probabilities of matrices with at least i 0-lines (columns or rows), the equation (1.6) is the inclusion—exclusion principle and the equation (1.7) follows from an analysis of matrices with h 0-rows and i-h 0-columns. Having

 S_i = \sum_{h=0}^i \left({n\atop h}\right)\left({n \atop {i-h}}\right)\frac{\left({(n-h)(n-i+h) \atop N}\right)}{\left({n^2 \atop N}\right)},

the paper modestly states that "...clearly for each fixed value of i ... we have:"

 S_i = \frac{2^i e^{-ci}}{i!}(1+o(1))

Well, this was far from being clear to me. The easy part was:

 \left({n\atop h}\right)\left({n \atop {i-h}}\right) = \frac{n!}{h!(n-h)!} \frac{n!}{(i-h)!(n-i+h)!} = \frac1{i!} \frac{i!}{h!(i-h)!} \frac{n!}{(n-h)!} \frac{n!}{(n-i+h)!}=


=\frac1{i!}\left({i\atop h}\right) n(n-1)\cdots(n-h+1)\cdot n(n-1)\cdots (n-i+h+1)

For every fixed i the values of h are bounded, hence

 \left({n\atop h}\right)\left({n \atop {i-h}}\right) \sim \frac1{i!}\left({i\atop h}\right) n^h n^{i-h} = \frac1{i!}\left({i\atop h}\right) n^i

Now, the other part of S_i was less easy to deal with. Taking into account that (n-h)(n-i+h) = n^2-in-h^2, we rewrite:

\frac{\left({n^2-in-h^2 \atop N}\right)}{\left({n^2 \atop N}\right)} = \frac{(n^2-in-h^2)(n^2-in-h^2-1)\cdots(n^2-in-h^2-N+1)N!}{N! n^2(n^2-1)\cdots(n^2-N+1)} =

= \prod_{j=0}^{N-1} \frac{n^2-in-h^2-j}{n^2-j} = \prod_{j=0}^{N-1}\left({1-\frac{in+h^2}{n^2-j}}\right)

Estimating the multiples, we obtain:

\left({1-\frac{in+h^2}{n^2-N+1}}\right)^N \le \prod_{j=0}^{N-1}\left({1-\frac{in+h^2}{n^2-j}}\right) \le \left({1-\frac{in+h^2}{n^2}}\right)^N

The upper bound is asymptotically equivalent to

e^{-\frac{in+h^2}{n^2}N} \sim e^{-\frac{in(n\log n + cn + o(n))}{n^2}} \sim e^{-i\log n - ci} = n^{-i} e^{-ci}

Similarly, for the lower bound is asymptotically equivalent to

e^{-\frac{in+h^2}{n^2-N+1}N} \sim n^{-i} e^{-ci},

which implies the product itself has the same asymptotics. Combining all parts of S_i together we end up with:

S_i \sim \sum_{h=0}^i\frac1{i!}\left({i\atop h}\right)n^in^{-i}e^{-ci} = \frac{e^{-ci}}{i!} \sum_{h=0}^i \left({i\atop h}\right) = \frac{2^i e^{-ci}}{i!},

finally arriving to what was "clear" for Erdös and Rényi.

The next problem was between equations (1.11):

Q_k(n,N)\le 2\left({n\atop k}\right) \left({n\atop k+1}\right) \left({k+1\atop 2}\right)^k \frac{\left({n(n-k-1)+k(k-1)\atop N-2k}\right)}{\left({n^2\atop N}\right)}

and (1.12):

Q_k(n,N)\le \left({\frac{A\log^2n}{\sqrt{n}}}\right)^k\text{ for }k=1,2,\ldots,\left[{\frac{n-1}2}\right],

hidden by a very modest "thus".

In the latter equation A is some constant, depending only on c. Transforming the first three binomial coefficients in (1.11) relies upon the inequality \frac{k^k}{k!}\le e^k which is a simplified version of Stirling's approximation. Hence:

2\left({n\atop k}\right) \left({n\atop k+1}\right) \left({k+1\atop 2}\right)^k \le 2\frac{n^k}{k!} \frac{n^{k+1}}{(k+1)!}\left({\frac{(k+1)k}2}\right)^k =

= \frac2{k+1}\frac1{2^k}n^{2k+1}\frac{k^k}{k!}\frac{(k+1)^{k+1}}{(k+1)!} \le \frac{(ne)^{2k+1}}{2^k}.

The other part is a bit trickier. The first thing to notice is that for the values of k we consider, the inequality k\le n/2+1 holds. Therefore n(n-k-1)+k(k-1)\le n^2-nk-n+kn/2 = n^2-n-kn/2. We then proceed:

\frac{\left({n(n-k-1)+k(k-1)\atop N-2k}\right)}{\left({n^2\atop N}\right)}\le \frac{\left({n^2-n-nk/2\atop N-2k}\right)}{\left({n^2\atop N}\right)} =

= \frac{(n^2-n-nk/2)\cdots(n^2-n-nk/2-(N-2k)+1)N!}{(N-2k)!n^2(n^2-1)\cdots(n^2-N+1)}

The nominator of the fraction contains N-2k multiples besides {N!}, while the denominator has N multiples, so we add 2k more multiples to obtain

\left({\prod_{j=0}^{N-1}\frac{n^2-n-nk/2-j}{n^2-j}}\right)\frac{N!}{(N-2k)!(n^2-n-nk/2-(N-2k))\cdots(n^2-n-nk/2-N+1)}.


Partly cancelling out the factorials we arrive to:

\left({\prod_{j=0}^{N-1}\frac{n^2-n-nk/2-j}{n^2-j}}\right) \left({\prod_{m=0}^{2k-1}\frac{N-m}{n^2-n-nk/2-N+1+m}}\right)


For the first product we estimate:

\prod_{j=0}^{N-1}\frac{n^2-n-nk/2-j}{n^2-j} \le \left({1-\frac{n+nk/2}{n^2}}\right)^N\le e^{-\frac{n+nk/2}{n^2}N}=

(taking into account that N=n\log n +cn+o(n))

=e^{-\log n-c-o(1)}e^{-\frac{k}2\log n - ck/2 - ko(1)}

Combining this with the previously obtained estimate for the first multiples of the (1.11) equation's left-hand side expression, we arrive to

Q_k(n,N) \le \left({\frac{\tilde{A}}{\sqrt{n}}}\right)^k n^{2k} \left({\prod_{m=0}^{2k-1}\frac{N-m}{n^2-n-nk/2-N+1+m}}\right).

The only thing that remains is to show that

\frac{n(N-m)}{n^2-n-nk/2-N+1+m} \le B\log n

for some constant B (B=4 should be enough, I guess), every m and large enough values of n. This altogether gives us the equation (1.12) finally.

The inequalities in paragraph 2 (transition from (2.6) to (2.7) and from (2.9) to (2.10)) are proved pretty much along the same lines. The only difficulty I noticed is that the proof of (2.10) for k=\left[{\frac{n-1}2}\right] should be carried out separately from other values of k, being the only case for which the inequality k+1\le n/2 does not hold.

I do hope my commentary will someday save somebody the pain of getting through the equations of this paper.

Оставить комментарий

Тема WordPress и иконки разработаны N.Design Studio
© 2018 Страница Алексея Яшунского RSS записей RSS комментариев Войти