Posts Tagged ‘publications’

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.


July 5, 2010
  1. I have this reading course “Advanced Random Graph Theory” with Nick for which I have to read and solve exercises, and the topics are foreign to me (though fortunately I have the necessary background to read them properly).
  2. I am TA for the course “Linear Optimization” for which I have to grade many assignments weekly, which takes a great amount of time, and I hate grading.
  3. For my research, I am working on various problems about the Cops and Robbers game. The first problem is, what is the cop number of d-regular random graphs? As this has (almost) been resolved for G(n,p), this problem is likely to be solved. The second problem is, what can we say about the game when the robber is faster than the cops? This paper inspired me to think about this problem. And I settled new lower bounds for the maximum cop number of an n-vertex graph when the speed of robber is between 2 and 6. (Hoorray, I am going to publish it!)
  4. I am trying to gain knowledge about various topics which I might like to pursue in my PhD. I am looking for topics which are somewhat more applied than what I am currently doing but abstract enough for me to enjoy! Examples include bioinformatics, multi-agent systems and social networks. I have to talk with friends and read random papers.
  5. I am reading the book A Mathematician’s Apology, by G.H. Hardy. He is a famous mathematician and talks about life and pursuing mathematics as a profession and what should a man do in his life etc. It is a great book and I think will help someone like me who is struggling with himself deciding what to do in life.

my approximation algorithms talk and some other news

April 8, 2010

  1. Yesterday I had a talk for the “approximation algorithms” course. The title of my talk was “Approximating the Number of Perfect Matchings in Bipartite Graphs” and I presented an algorithm of Jerrum and Sinclair, developed in 1988. I had spent a lot of time (3-4 days) preparing the slides (actually for this talk I learned to use the Beamer package to create LaTeX-based presentations, and the TikZ/PGF package for creating the graphics) and the result was very good, I liked my slides, and I got positive feedback from the audience. The slides can be found here. In a part of the algorithm I described, a Markov chain was used, and to introduce the concept to the audience, I used the intuition of “random walk on a graph” instead of the formal definition. The picture you see above was one of the slides used to illustrate the distribution of a random walker (a happy ghost in this picture) on the vertices of the underlying graph. I was really relieved after the talk since I am not used to present in English.
  2. The paper I posted about two months ago was accepted in Ars Combinatoria. Another paper which I worked on in the same team (when I was an undergrad) was also recently accepted to appear in Graphs and Combinatorics after some revisions, yoohooo !
  3. The Winter 2010 term is almost finished – I have one final exam (integer programming) and I have to submit the final report for approximation algorithms. I spent most of my time on the courses, and I also read a few papers of Nick (my supervisor).
  4. My plan for the next term: I will attend the First Montreal Spring School in Graph Theory in May, and when I return, I will focus on my research (random graphs) and read related stuff (some ideas: The probabilistic methods by Alon-Spencer, Randomized Algorithms by Motwani-Raghavan, Lectures on Random Graphs and Survey on Regular Random graphs by Nick). I won’t take any course but may audit computational geometry from computer science. What a pity I didn’t attend the “Multi-agent Systems” course offered in Winter 2010 in CS.
  5. A graph theory problem: Prove that there exists an integer k, such that for any connected graph G with more than 2 vertices, one can assign a label from {1,2,…,k} to each edge, such that the sum of the labels of edges incident to every vertex defines a proper coloring for the graph. It has been conjectured that k=3 works, and the currently best known bound is k=5. I think it is a cute problem, see here for more info.

Revised “Nowhere-zero Unoriented Flows in Hamiltonian Graphs” submitted

February 2, 2010

This work was done almost two years ago, when I was an undergrad in Sharif. After being rejected two times, the Ars Combinatoria journal accepted to publish it after revisions. The referee have made quite a few comments/suggestions. I was modifying it during the last 12 days. Today the final (revised) version was created, approved by all authors and sent to the corresponding author. If accepted, this would be my first publication. Well done and congratulations!