June

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.

First Montreal Spring School in Graph Theory

May 13, 2010

I am attending this one-month summer school in Structural Graph Theory, which is held in Montreal. It is a high-level school with world-class speakers, and I am really enjoying it. We have two classes everyday for four weeks, making a total of 40 lectues.

Paul Seymour talks about excluding induced subgraphs, and, in particular, will sketch a proof of the Strong Perfect Graph Theorem, which he (together with Chudnovsky, Robertson and Thomas) has proved in 2001. This was a huge result, with a 150-pages proof. Not only is he a great problem-solver, but also he is a great teacher. I really do enjoy sitting in his class. He is so smart, draws lots of pictures, and always proves what he wants in a bottom-up way; That is, unlike many others who first write a Theorem statement formally and then write the proof, he first describes intuitively why such a Theorem has to be true, and only then writes it down.

Maria Chudnovsky (the picture is a bit old) also talks about excluding induced subgraphs, but her lectures are independent of the Paul’s. She is also smart and a good instructor (she was Paul’s PhD student and must have learnt a lot from him).

Bruce Reed talks about excluding minors from graphs. In particular he talks about Robertson and Seymour’s Graphs Minor Project. He is a great researcher. Sometimes his lectures are confusing for me, in particular when he talks about planar graphs. Fortunately he has now turned to tree decompositions, which I am a little familiar with.

To summarize, I am so glad that I am attending this school. Structural Graph Theory is really nice (though hard to prove new results) and I enjoy sitting in the classes and working on the assignments. It is like I am back in the IMO training camp (7 years ago)! The city of Montreal is also very nice. Here you see a photo I took in the botanical garden, which I went to see on May 8th.

a nice probabilistic argument by Alon

April 12, 2010

These days I am reading “Probabilistic Methods for Algorithmic Discrete Mathematics.” Alon‘s probabilistic proofs are usually beautiful. This one (Theorem 6.1) that I saw today was not an exception. It is really simple to understand, but also very elegant. I can’t help admiring it. It is brilliant. That’s the reason that I like the probabilistic method: because it is full of beautiful proofs. I wish I could write a similar proof someday.

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.

Integer Programming

March 25, 2010

I really don’t like Integer Programming. But I think having the course has had benefits for me:

  1. I figured out that the decision of changing supervisor was a correct one (my former supervisor worked on IP).
  2. I can understand (feel) what one means when she says “I don’t like this course!”
  3. I can evaluate my performance on something that I don’t like but I have to do.

PS – I want to learn beamer for my approximation algorithms presentation. Hoorraay !

Does Coke and Pepsi taste differently?

March 13, 2010

In a talk of John Watrous on Friday in Tutte’s seminar, he proposed the above problem as an interesting example of the power of interactive proofs over classical proofs. To make it precise, suppose that I believe that Coke and Pepsi taste differently plus I can actually feel the difference; and you are really curious if I am right. Well, how can I convince you (give you a “proof”) that they taste differently? The proof needs to have the property that if I am right then you should detect it, and if I am wrong then you should detect it with high probability (say, 99.9 percent).

.

.

.

It is difficult, eh?

.

.

.

No, it is simple. Just make me blindfold, give me 1000 glasses of Coke/Pepsi and I have to categorize them. If I do it correctly, then you will be convinced that I can feel the difference. This is the point: The proof is done by “interaction between you (verifier) and me (prover),” and not by simply giving a certificate (as in the case of classical proof). Well, if I am a liar, then there is a tiny probability that I can fool you; but we usually ignore such small probabilities in life!

The difference between an optimizer and a mathematician

February 15, 2010

Optimizer (E.g. algorithm designer): This theorem is good because you can devise an algorithm using it.

Mathematician: This theorem is good because it has a nice proof, or it is surprising, or it generalizes many known ideas.

The PCP Theorem, and computational complexity

February 8, 2010

One reason I like computational complexity is because it’s mysterious: you see surprising results that don’t agree with your common sense. The first example was the equality NL = co-NL, which I saw a few years ago, and has a very elegant proof. And the second example was the PCP e, i.e. NP = PCP (log n, 1), which is quite surprising, and the proof is perhaps very complicated. That’s why you can never be sure that NP\P is nonempty, even if  everyone believes it.

For almost the same reason, I liked probability theory when I was in high-school: it is mysterious, and there were lots of paradoxical problems related to probability. Well, when I studied formal probability theory (Kolmogorov axioms etc.) there wasn’t any paradoxes anymore (fortunately?), but I still like it, because of its surprisingly strong applications in graph theory and algorithms.

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!

The PTAS for Euclidean MST

January 29, 2010

The Arora’s PTAS for Euclidean MST is huge. A breakthrough. A great paper full of original ideas. Although it is too complicated for me to understand fully, I can’t help admiring it. I wish I can write one paper like this in my academic life!