## Posts Tagged ‘random graphs’

August 25, 2010
- The reading course (on random graphs) I had in summer with Nick (my supervisor) has finished, and it was really good: I was introduced to the area of randomized structures (esp. graphs) and processes and solved a few problems. I also became comfortable with asymptotic notations and little/big Oh’s are not scary anymore!
- My research is progressing well: I have proved a bunch of small results on Cops and Robbers. First, I found a 3-approximation algorithm for calculating the cop number of an interval graph, assuming the robber has infinite speed. Second, I proved that the cop number of a random regular graph is a.a.s O(n^0.81) if d = n^o(1).
- These days I am reading The Probabilistic Method by Alon and Spencer. The method is quite nice, usually results in beautiful proofs, and the book is really well-written. I am reading one chapter per day in order to finish it before the new term.
- Next term I am going to take Algorithmic Game Theory and a bioinformatics course from CS department. I am already excited about them. It is cool that so many good courses (with a broad range) are offered in UWaterloo.

Tags:cops and robbers, probabilistic method, random graphs

Posted in news | Leave a Comment »