• I have a new paper published in Graphs and Combinatorics! It’s my favourite paper to come out of my research with Jing Huang at the University of Victoria — the third written chronologically, and the last to be published. The main result is that the structure of monopolar partitions in claw-free graphs can be fully understood by looking at small subgraphs and following their direct implications on vertex pairs.

• This Atlantic interview with SimCity designer Stone Librande has stuck with me.

We were originally just going to model real cities, but we quickly realized there were way too many parking lots in the real world and that [SimCity] was going to be really boring if it was proportional in terms of parking lots.

Stone Librande
(more…)
• One of the most recognizable features of Japanese architecture is the matted flooring. The individual mats, called tatami, are made from rice straw and have a standard size1 and 1×2 rectangular shape. Tatami flooring has been widespread in Japan since the 17th and 18th centuries, but it took three hundred years before mathematicians got their hands on it.

(more…)
• When the Ontario cities of Fort William and Port Arthur amalgamated in 1970, residents voted for a new name for their new city.

The result deserves a place of honour in voting theory textbooks.

• I have a new paper with Jing Huang in Graphs and Combinatorics! This was the culmination of my undergraduate research, and shows that a single strategy can be used to solve the monopolar partition problem in all graph classes for which the problem was previously known to be tractable, including line graphs and claw-free graphs.

This research was completed in the summer of 2010, my last undergraduate research term. I am grateful to NSERC for funding my work with a Undergraduate Student Research Award, and to my supervisor and coauthor Jing Huang.

• Image Evolution is a very interesting Javascript tool based on Roger Johansson’s Evo-Lisa idea. It uses a genetic algorithm to represent images as a collection of overlapping polygons.

We start from [a set of random] polygons that are invisible. In each optimization step we randomly modify one parameter (like color components or polygon vertices) and check whether such new variant looks more like the original image. If it is, we keep it, and continue to mutate this one instead

Altered Qualia

Just feed it an image and hit start, and a random collection of coloured polygons will gradually evolve into a cool abstract rendition of your picture.

• Ever wonder why LaTeX doesn’t provide a way for printing the title and author once `\maketitle` has been issued? I did. So I asked a question on the TeX StackExchange and received an interesting answer. Turns out it’s an artifact of the times when memory was in extremely short supply.

The main reason was “main-memory” back in those days. LaTeX was effectively eating up half of the available space just through macro definitions. So with complicated pages or with some picture environments etc you could hit the limit. So freeing up any bit was essential and you still see traces of this in the code.

Frank Mittelbach

Dark times!

• I have successfully defended my master’s thesis on graph-transverse matching problems! It considers the computational complexity of deciding whether a given graph admits a matching which covers every copy of a fixed tree or cycle.

The thesis is related to my previous work on cycle-transverse matchings and P4-transverse matchings and, roughly speaking, shows that H-transverse matchings are NP-hard to find when H is a big cycle or tree, and tractable when H is a triangle or a small tree.

(more…)
• I defend my thesis in two weeks, but I’ll be prepared for the snake fight portion thanks to McSweeney’s guide.

Do I have to kill the snake?

University guidelines state that you have to “defeat” the snake. There are many ways to accomplish this. Lots of students choose to wrestle the snake. Some construct decoys and elaborate traps to confuse and then ensnare the snake. One student brought a flute and played a song to lull the snake to sleep. Then he threw the snake out a window.

Are the snakes big?

We have lots of different snakes. The quality of your work determines which snake you will fight. The better your thesis is, the smaller the snake will be.

Luke Burns
• In 1852, then-student Francis Guthrie wondered any if possible map required more than four colours. By the end of the century, Guthrie and his fellow colonists had drawn a map on Africa that needed five.

(more…)
• A little while ago, I did some sleuthing to find out the Erdős number of Brian May, astrophysicist and guitarist from Queen. My travels led me to Timeblimp, who threw together three measures of professional collaboration to make a rather fun parlour game. Assuming that the people in your parlour are three kinds of nerds and enjoy long and complicated internet scavenger hunts. Which I am and I do.

(more…)
• Pokémon Gold and Silver introduced the roaming legendary beasts: three one-of-a-kind Pokémon that move from route to route instead of sticking to a fixed habitat. Catching a roaming Pokémon amounts to winning a graph pursuit game — so what can we learn about it from the latest mathematical results?

(more…)
• Dr Robb Fry, one of my professors from my Thompson Rivers University days, passed away earlier this year at far too young an age. Robb was a real character, a great teacher, and a lot of fun to know.

I took my second course in linear algebra with Robb, and it was one of the most entertaining courses of my first two years. While visiting my parents over the holidays, I dug out my course notes — the only full set of notes I ever took in undergrad — so I could share some memorable episodes from my time with him.

(more…)
• Earlier this year, I presented the first results of what would become my master’s thesis at the International Workshop on Combinatorial Algorithms. The paper, coauthored with Jing Huang and Xuding Zhu, has now been published in the LNCS proceedings. It studies the computational complexity of the following problem: in a given graph, is there a matching which breaks all cycles of a given length?

I am grateful to NSERC for funding this research with a Alexander Graham Bell Canada Graduate Scholarship.

• Shortly after solving the monopolar partition problem for line graphs, Jing Huang and I realized that our solution could be used to solve the “precoloured” version of the problem, and then further extended to claw-free graphs. Jing presented our result at the French Combinatorial Conference and the proceedings have now been published in Discrete Mathematics.

• I’ve published a new paper in the SIAM Journal on Discrete Mathematics! The work is the result of the research term I took as an undergraduate in the summer of 2009. It studies the edge versions of the monopolar and polar partition problems, and presents a linear-time solution to both.

I am grateful to NSERC for funding my work with a Undergraduate Student Research Award, and to my supervisor and coauthor Jing Huang.

• I was recently told that European hotels are subject to a reduced VAT rate. They must have a big lobby.

• My most recent talk in UVic’s discrete math seminar presented three poetic proofs by Adrian Bondy… and three actual poems summarizing the ideas in each one.

(more…)

Pages: 1 2 3 4

• The UK House of Lords recently debated a pest control problem in a scene straight out of a sitcom:

My Lords, I do not actually deal with the economy. I am glad to say that that would be above my pay grade, whereas trying to deal with the mice is probably just about right for me.

The Chairman of Committees

Another choice quote now immortalized in Hansard:

I invited Members of the House to telephone when they saw mice. The trouble is that when the person at the other end of the helpline goes to check this out, very often the mouse has gone elsewhere.

The Chairman of Committees
• If you’ve heard of Erdős numbers, Erdős-Bacon numbers, and the fact that Queen lead guitarist Brian May has a PhD, you may have wondered whether Brian May has a well-defined Erdős number.

As a matter of fact, he does! I traced down a collaboration path of length seven through a 1972 paper he published in Nature.

(more…)