Category Archives: Random graphs

On the influence of the seed graph in the preferential attachment model

    The preferential attachment model, introduced in 1992 by Mahmoud and popularized in 1999 by Barabási and Albert, has attracted a lot of attention in the last decade. In its simplest form it describes the evolution of a random tree. Formally we denote by … Continue reading

Posted in Random graphs | 6 Comments

Random-Approx 2013

Last week I attended the Random-Approx conference at Berkeley. I missed quite a few talks as I was also settling in my new office for the semester at the Simons Institute so I will just report on the three invited talks: Luca Trevisan gave a … Continue reading

Posted in Random graphs, Theoretical Computer Science | 2 Comments

Guest post by Philippe Rigollet: Estimating structured graphs

Last wednesday, Sourav Chatterjee was speaking in the Mathematics Colloquium here at Princeton. While he is most famous for his contributions to probability, especially using Stein’s method, this talk was rather statistical. The problem was interesting and its solution simple enough that … Continue reading

Posted in Random graphs | Leave a comment

Proof of the lower bound

Our proof of the lower bound for the clique number of random geometric graphs (see Theorem 1 in the previous post) is a little bit contrived, but it might actually have some value. Our approach can be described as follows. … Continue reading

Posted in Random graphs | Leave a comment

Clique number of random geometric graphs in high dimension

I would like to discuss now another class of random graphs, called random geometric graphs. In general a random geometric graph arises by taking i.i.d. random variables in some metric space, and then putting an edge between two of these random … Continue reading

Posted in Random graphs | Leave a comment

An unpleasant calculation?

At the end of my previous post I claimed that proving that tends to when tends to infinity and was unpleasant. It appears that I was wrong, and I would like to show here a simple proof that was suggested … Continue reading

Posted in Random graphs | 1 Comment

Welcome! (with random graphs)

Welcome to the ‘I’m a bandit’ blog! If you are curious about this title, you can check my newly published book. However, despite its name, this blog will not be about bandits, but rather about more general problems in optimization, … Continue reading

Posted in Random graphs | 2 Comments