Archive for January, 2010

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!


“Graph Theory” as seen by Bondy and Murty

January 27, 2010

“Like number theory, graph theory is conceptually simple, yet gives rise to challenging unsolved problems. Like geometry, it is visually pleasing. These two aspects, along with its diverse applications, make graph theory an ideal subject for inclusion in mathematical curricula.”

J. A. Bondy and U. S. R. Murty, September 2007

(Preface of their book “Graph Theory”)

Graphics in LaTeX: TikZ and PGF package

January 26, 2010

I don’t want to look ungrateful, but one of the main drawbacks of LaTeX is that it’s not easy to handle graphics there. I’m used to use the built-in “picture” environment, but that’s a headache as soon as your figure becomes complicated enough.

Recently one of my friends told me about the TikZ & PGF package (TikZ is the shell, PGF is the core) and I looked at the manual today: it looks promising. For instance the figure you see at above has been generated using <50 lines of code. The manual is very long but I will try to read it as soon as I get some free time. You can download the package here and the manual from here.

Thomas’ tutorial and CO754 Assignment2

January 20, 2010

I have recently studied Thomas’ lecture notes on tree-decompositions on graphs, which gives the reader an insight into the concepts of tree-decomposition, tree-width etc. It had a understand-through-solving-problems approach that I believe  is very nice and instructive:

But the interesting part was that once I saw the problems of the 2nd assignment of approximation algorithms, I found that one of the optional problems is straightforward as the idea was covered in the notes. Specifically, problem 4(b) is easy if you study paragraphs C5-C9 of the notes.

copying posts into facebook

January 17, 2010

Well, these days everybody uses Facebook. It has an application called “Notes” that is like a weblog. It is not rich at all, but a nice feature is that you can configure it to import posts automatically from an external blog into it (using RSS and stuff). I am already importing my other blog into it, and I had the idea of having the posts of here auto-imported to there; but I found out that, unfortunately, it can import only one RSS 😦 So I will try to copy my posts into facebook manually until I find some more reasonable solution.

PS – I have added a few links at the right. Enjoy!

Hello world!

January 16, 2010

And I finally started a new weblog! I already have a blog, in which I write about everyday life, and is in Persian. This new blog will be in English (let’s say for practicing writing in English) and its content shall be mostly mathematical and/or academic. I felt that I really want to talk about such topics (perhaps for my own review in the future), and some readers of the old one might be bored reading such material, so I decided to dedicate a whole new blog.

About the name: The meaning is left to the imagination of the reader! Well, I like Graph Theory, and the postfix’s idea came from my friend’s blog.

About me: I got my bachelor’s degree(s) in Sharif University of Technology, Tehran, Iran, in August’09. I did a double-major program, in Computer Engineering and Mathematics. I have started a Master’s program in the Department of Combinatorics and Optimization, University of Waterloo. According to my homepage, my research interests are:

  • GRAPH THEORY (all branches): I have done research in Flows in Graphs, Graph Homomorphisms and Graph Searching
  • THEORETICAL COMPUTER SCIENCE (or any other field with a strong connection with mathematics), for example:
  • Combinatorial Optimization

  • Computational Geometry
  • Applications of Probability in Theoretical Computer Science

  • Computational Complexity

Maybe that’s enough for the first post, so see you later!