Posts Tagged ‘random graphs’


August 25, 2010
  1. 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!
  2. 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).
  3. 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.
  4. 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.