Remembering Robb Fry
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 (the Robb Fry Appreciation Group on Facebook had dozens of members from multiple universities even before he died).
I took my second course in linear algebra with Robb, and it was one of the most entertaining courses of my first two years. My course notes – the only full set of notes I ever took in undergrad – were naturally interspersed with records of Robb's regular witty remarks and quotable quotes. When visiting my parents over the holidays, I dug out these notes, so I thought I'd share some of the memorable episodes from my time with him.
ROBB: Can I call this function \(\tilde{f}\) "f twiddle" and this one \(\tilde{\tilde{f}}\) "f twiddle twiddle"?
CLASS: Sure.
ROBB: So take \(\tilde{\tilde{f}}\ {}^*\) "f twiddle twiddle little star..."
(Introducing the notation ∃!)
ROBB: It means "there exists a unique..." but I always read it like it's a William Shatner thing. THERE EXISTS!
ROBB: You're defining this... it doesn't come from God. Especially since God doesn't exist.
CLASS: Ooooooooooooh
ROBB: Oooh, he has an opinion!
ROBB: An oval...
CLASS: Don't you mean an ellipse?
ROBB: Yeah, whatever the real term for that is.
ROBB: I'm going to avoid yellow chalk today, because I have a suspicion that one day they'll find that the stuff that makes it yellow is toxic. That's going to be someone's Ph.D. thesis one day, The Toxic Effects of Yellow Chalk, and I don't want to be part of the study group.
(After introducing the kernel as "the set of all stuff that gets killed by a map")
ROBB: The best bumper sticker I've ever seen had a picture of the colonel from KFC with "I am dead."
ROBB: If you're ever reading a paper, and they say they have to prove a technical lemma, brace yourself for some HORRIFIC MATH.
(Talking about stable/invariant sets)
ROBB: I use "invariant" instead of "stable." A stable set sounds like something for horses. I like horses, mind you, but they shouldn't be confused with mathematics.
You taught me, inspired me, and motivated me to continue on the path to becoming a mathematician. But more importantly, it was a lot of fun to know you. Thanks, Robb.
Graph Theory in Cricket?
One of the secretly fun parts of keeping a personal website is getting to look at its visitor statistics. Most of the hits I get are pretty predictable: Google searches for "Ross Churchley" or "monopolar graphs" end up here, and there's a steady trickle of people looking for Brian May's Erdős number or an "Edmonton Eulers" logo. But lately I've gotten a few hits from people looking for something I don't have on this site: "uses of graph theory in cricket."
So if you've arrived at this website hoping for applications of graph theory in the great sport of cricket: I hate to disappoint you, but I don't have much. I thought about it long and hard, but I couldn't come up with anything that directly applies a pure graph theoretic result. Certainly there's a great deal of statistics involved in cricket, most famously the method derived by Duckworth and Lewis to set a target after a rain delay. There's quite a bit of geometry (and possibly some stochastic programming) in setting a field. There's a ton of interesting mathematics from a bunch of different fields behind Hawk-Eye; maybe they use graph theoretic algorithms under the hood? Your club league might benefit from some of the work done on various scheduling problems, and the international travel schedules could use some combinatorial optimization. Data science can apparently help you bowl out Tendulkar and applied math can help you decide when to declare. Graph theory can be a helpful tool for solving a number of these problems, but as for a pure graph theoretic situation that crops up in cricket? Can't think of any. Sorry.
(If you can think of a practical application of graph theory to the great sport of cricket, let me know in the comments!)
IWOCA 2011
IWOCA 2011 group picture taken by the organizers
Two weeks after hosting CanaDAM, UVic was also the home of this year's International Workshop on Combinatorial Algorithms; there I presented a paper by myself, Jing Huang, and Xuding Zhu on cycle-transverse matchings. In the paper, we consider the Ck transverse matching problem: given a graph G, is there a matching M such that G-M contains no cycles of length k? We gave a polynomial-time algorithm for the case k=3, but showed that the problem is NP-complete when k ≥ 4. In fact, when k ≥ 4 is even, the problem is still NP-complete for bipartite graphs.
The case k = 4 has connections with the tatami tiling problem, as Frank Ruskey pointed out to us.
University vs Colts
Although there was no rain in the forecast, dark and threatening clouds blocked the sun from shining on the Metchosin cricket ground. The University team was playing Colts CC, the youth team led by our own Ram Meyyappan. As they were shorthanded, we brought along a few extra players to lend them. With a chilly breeze setting in, we got started as soon as we could. University won the toss and elected to bat.
CanaDAM 2011
CanaDAM group photo taken by the conference organizers
This year, I had the pleasure of attending (and helping organize) CanaDAM, which was held at UVic. I gave a talk in the Structured Graphs and Algorithms session, titled "Partitioning graphs via edge-coloured homomorphisms". In it, I announced some recently-submitted results on the monopolar partition problem and related problems. The main result unifies all currently known polynomial-time monopolarity results: it reduces the problem to 2SAT for a very large graph class, which contains
- claw-free graphs
- chordal graphs
- co-comparability graphs
- all graphs with no induced cycle of length ≥ 5
A similar technique can be used to solve the unipolar partition problem – which asks whether a (general) graph can be partitioned into a clique and a disjoint union of cliques – in polynomial time.
University vs Wicket Maidens
Our last game at UVic was against the Wicket Maidens. As the only all-women's team in the midweek league, the Wicket Maidens offer a unique challenge: each of their runs is matched with a penalty run, doubling their batting score. Playing in a fast artificial field, we had to make sure to set a high target. University won the toss and elected to bat.
University vs Metchosin
This match was the first of four scheduled at the artificial fields of UVic. I actually missed this one, being out of town visiting family, but I managed to reconstruct the match from our scorebook. UVic won the toss and elected to bowl first.
Death and Taxes Canada
With another election coming up, I thought it would be a good idea to revisit this post about public spending. The political media is naturally concerned with changes — a few billion dollars in new programs here or spending cuts there — but it's hard to understand changes without having some sort of baseline. This chart (which I made from the Treasury Board's 2011 estimates) should give some context to the coming weeks' campaign.
Edit: In addition to the spending on this chart, the federal government spends $30.3 billion on federal debt charges. Forgot to put that in, and it's too late to add it now... It'll have to wait to the next revisit!
Beagle vs University
The opening match of the 2011 Midweek League season, between us and the Beagle Pub cricket club, turned out to be quite an exciting affair. Due to the weather and poor light — there was a strange mix of sunset and light showers — it was agreed to abbreviate both teams' innings to 14 overs. Beagle won the toss and elected to bat first.
Cops and Drunken Robbers on MathOverflow
For the last few days, I've been hooked by a simple cops-and-robbers problem which has little to do with my thesis research. A cop and a robber occupy some two vertices of a graph. For reasons left to the imagination, the robber moves at random, moving at each step to a randomly chosen neighbour of his current vertex. The cop wants to catch the robber as quickly as possible. How do we find a strategy for the cop which minimizes the expected capture time?
In the hopes of freeing up some brainpower for the work I'm supposed to be doing right now, I've turned to the collective wisdom of MathOverflow. If you know of any work that has been done on this problem, I'd be much obliged if you added an answer to my question there.
