Math

Rule of twelfths

The rule of twelfths is a memorable way to approximate a sinusoidal curve by twelve equally-spaced line segments of slope

¹⁄₁₂, ²⁄₁₂, ³⁄₁₂, ³⁄₁₂, ²⁄₁₂, ¹⁄₁₂, ⁻¹⁄₁₂, ⁻²⁄₁₂, ⁻³⁄₁₂, ⁻³⁄₁₂, ⁻²⁄₁₂, and ⁻¹⁄₁₂

respectively. It rounds $\frac{\sqrt{3}}{2} \approx \frac{5}{6}$ but otherwise uses exact values along the curve.

How to catch legendary Pokémon (in practice)

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?

A brickwork fractal

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.

A submodular measure and approximate Gomory–Hu theorem for packing odd trails

This paper, published after I left academia, explores the "perimeter" measure that plays a key role in my doctoral research.

Odd disjoint trails and totally odd graph immersions

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.

Weak duality for packing edge-disjoint odd trails

This paper, coauthored with my supervisor Bojan Mohar and colleague Hehui Wu, was the first entry in my doctoral research into graph immersions with parity restrictions.

On the polarity and monopolarity of graphs

This is my favourite paper to come out of my research with Jing Huang at the University of Victoria, and the last one 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.

Tatami tilings

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

Solving partition problems with colour-bipartitions

This paper was the culmination of my undergraduate research on monopolar graphs with Jing Huang. It 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.

On graph-transverse matchings

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.

Colonialism and the 4-Colour Theorem

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.

How to catch legendary Pokémon (in theory)

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?

Complexity of cycle-transverse matching problems

This paper by me, Jing Huang, and Xuding Zhu, gives the first results of what would become my master’s thesis. 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?

List-monopolar partitions of claw-free graphs

Shortly after solving the monopolar partition problem for line graphs, Jing 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.

Line-polar graphs: characterization and recognition

This paper 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.

The monopolar partition problem in restricted graph classes

A graph is called monopolar if its vertices can be partitioned into an independent set and a disjoint union of cliques. My undergraduate research with Jing Huang studied monopolar partitions in line graphs, claw-free graphs, and other graph classes.

Graph theory haiku

My most recent talk in UVic’s discrete math seminar presented three poetic proofs by Adrian Bondy.

Vizing's Theorem haiku

Induction on n.
Swap available colours
and find SDR.

Ore's Theorem haiku

A red-blue

K_n

:
bluest Hamilton circuit
lies fully in

G

Brooks' Theorem tanka

Greedily colour,
ensuring neighbours follow
all except the last.

Choose the last vertex wisely:
friend of few or of leaders.

Exponential growth in Katamari Damacy

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.