Posts Tagged ‘cops and robbers’

My first solo publication, in Discrete Mathematics

October 31, 2010

My BSc project was a survey on Cops and Robber game. I also studied the capture time of Cartesian product of trees, and in Nowrooz holidays (March 2009) I proved that the 2-capture time of a Cartesian product of two trees is half its diameter, and the 2-capture time of an mxn grid is (m+n-2)/2. I submitted my work in January 2010 to Discrete Mathematics and it was accepted in October 2010. This is my first solo publication, it is in a well-known journal, so I am happy 🙂

The manuscript can be found here and the online published version can be found here.

The story of my paper with Noga Alon

October 15, 2010

Well, in one of our meetings in August, Nick (my supervisor) told me that Noga Alon will visit UWaterloo in a few weeks, and I can give him a quick glimpse of my work on Cops and Robber game, and I said Ok, happy to know that I’ll meet him. He came in September and gave a talk in Tutte’s seminar. Next day Nick arranged a meeting in his office and I told Noga my work. He seemed interested, and proposed an idea that if correct, would’ve extended my result. With Nick’s help I worked on the idea for a week or two, and yeaaah … it worked! I was so excited, sent the proof to Nick, and he verified its correctness. Then I contacted Noga and asked if he’d like to be a coauthor, and he confirmed. He made a bunch of corrections and we submitted it. It’s a short paper however (7 pages).

Oh boy, if you’d told me an year ago that just an year after coming to Canada I’ll write a paper with Noga Alon, I would’ve considered it as a joke. But it really happened! Thank you God!

Some technical details: There was a recent preprint by Frieze et al., where they had considered the variation of Cops and Robber where the robber has speed s>1. For every s they had given a lower bound for the maximum cop number of a graph with n vertices in that variation. In summer I had worked on this problem and improved their bound for s<7 (here). I proved the cop number of an n-vertex graph can be as large as n^{s/s+1} when s=2,4. My proof uses regular graphs with large girth, which are called cages. I had also conjectured that this lower bound holds for larger values of s as well. There is an old conjecture of Bollobas about cages that implies my conjecture. Noga told me about regular graphs that don’t have large girths, but for every two close vertices, there are a constant number of shortest paths connected them. These graphs are enough for my proof, and their number of vertices are exactly what I wanted. Hoorraay.


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.