Страница Алексея Яшунского

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.