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.

## Archive for April, 2010

### a nice probabilistic argument by Alon

April 12, 2010### my approximation algorithms talk and some other news

April 8, 2010- 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.
- 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 !
- 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).
- 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.
- 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.