Archive for the ‘graphs’ Category

About a month ago, the Facebook Hacker Cup included a nice programming problem involving a certain kind of matching. The min-cost bipartite matching problem can be stated like this: You have a number P of people, and a number Q ≤ P of jobs. Each person is willing to do any of the jobs, but each person will charge a different price for each job. You are only allowed […]

Last week I was at the second Emléktábla workshop in Hungary. It was a great event and a chance to meet lots of other young mathematicians, and learn a lot. One problem which I woked on with János Barát, Filip Morić, and Zoltán Nagy, is the following. (The problem is due to Péter Maga.) Characterize all graphs which […]



Last weekend I went to a two-day workshop on combinatorics at the Max Planck Institut für Informatik. The place is sort of a European mecca for computer science, as it hosts a gigantic collection of post-docs and students, but had only one professor up until recently. In the city, nearly every restaurant has a logo […]

Math Circles


The University of Waterloo’s CEMC holds Math Circles in which they invite local grade 6-12 kids to come to the university one evening a week for math enrichment activities. In the past years I have participated for 2-3 weeks per year, running sessions on the topics of Game Theory and Conics (ellipses, parabolas, etc). This […]

My work on linear programs led me to read up on colouring arguments and eventually to post some remarks on the arXiv wherein I gave a proof ot the following. (See “graph” and “regular” on Wikipedia. A “spanning subgraph” is what you get when you delete some edges, but keep all the vertices.) For every […]

This one comes from Donald Knuth, who is rather well-known for writing a number of good books and inventing TeX (which is what mathy people use to make pretty formulas). Without further ado, here is the Las Vegas Theorem: Suppose we have a finite network of one-way roads containing a distinguished city, Las Vegas, with […]