# Tag: Math

• A while ago I arbitrarily decided that I needed a favourite three-digit number (don’t ask) and ended up choosing 216. It’s a nice cube number — 6×6×6 — and can also be expressed as a sum of three smaller cubes:

6^3 = 5^3 + 4^3 + 3^3
(more…)
• You can get a really good approximation of a sinusoidal curve from twelve equally-spaced line segments of slope 1/12, 2/12, 3/12, 3/12, 2/12, 1/12, -1/12, -2/12, -3/12, -3/12, -2/12, and -1/12, respectively.

This approximation, known as the rule of twelfths, rounds √3≈5/3​ but otherwise uses exact values along the curve.

(more…)
• Pokémon Gold and Silver‘s roaming legendary beasts move randomly from route to route instead of sticking to a fixed habitat. By analyzing their behaviour using the math of random walks on graphs, I can finally answer a question that’s bugged me since childhood: what’s the best strategy to find a roaming Pokémon as quickly as possible?

(more…)
• Brick pavements and tatami mats are traditionally laid out so that no four meet at a single point to form a ┼ shape. Only a few ┼-free patterns can be made using 1×1 and 1×2 tiles, but the addition of 2×2 tiles provides a lot more creative flexibility.

(more…)
• Although I’ve left academia, Bojan Mohar and I have published a new paper in the proceedings of SODA exploring the “perimeter” measure that plays a key role in my doctoral research. It is mostly based on Chapter 4 of my PhD thesis.

• I have succesfully defended my PhD thesis! It’s “packed” with results on graph immersions with parity restrictions, and “covers” odd edge-connectivity, totally odd clique immersions, and a new submodular measure that’s intimately connected with both.

I am grateful to NSERC for funding my degree with a Alexander Graham Bell Canada Graduate Scholarship, and to my supervisor Bojan Mohar.

(more…)
• I have a new paper, coauthored with my supervisor Bojan Mohar and colleague Hehui Wu and presented at the SIAM Symposium on Discrete Algorithms! It is my first foray into graph immersions with parity restrictions.

I am grateful to NSERC for supporting this research through an Alexander Graham Bell Canada Graduate Scholarship.

• 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.

• 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…)
• 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.

• 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…)
• 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…)
• 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…)
• 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.

• 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

• One of my favourite video games of all time is the inexplicable Katamari Damacy. Its quirky premise involves, as Wikipedia puts it, “a diminutive prince rolling a magical, highly adhesive ball around various locations, collecting increasingly larger objects until the ball has grown great enough to become a star.” In other words, it’s the most successful game ever made about exponential growth.

(more…)