## 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  vertices ( vertices in each part) with  edges has positive probability of containing a set of  independent edges as  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  are probabilities of matrices with at least  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  0-rows and  0-columns. Having

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

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

For every fixed  the values of  are bounded, hence

Now, the other part of  was less easy to deal with. Taking into account that , we rewrite:

Estimating the multiples, we obtain:

The upper bound is asymptotically equivalent to

Similarly, for the lower bound is asymptotically equivalent to

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

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

The next problem was between equations (1.11):

and (1.12):

hidden by a very modest "thus".

In the latter equation  is some constant, depending only on . Transforming the first three binomial coefficients in (1.11) relies upon the inequality  which is a simplified version of Stirling's approximation. Hence:

The other part is a bit trickier. The first thing to notice is that for the values of  we consider, the inequality  holds. Therefore . We then proceed:

The nominator of the fraction contains  multiples besides , while the denominator has  multiples, so we add  more multiples to obtain

Partly cancelling out the factorials we arrive to:

For the first product we estimate:

(taking into account that )

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

The only thing that remains is to show that

for some constant  ( should be enough, I guess), every  and large enough values of . 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  should be carried out separately from other values of , being the only case for which the inequality  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