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.
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.
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.
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.
CMS Winter Meeting 2010
I appreciate everyone who looked at my slides instead of out the window during my talk.
My talk at the Canadian Mathematics Society's 2010 Winter Meeting was my first-ever conference presentation. The talk was scheduled at 4:30 in a hotel suite halfway up the building, so we were treated to the beautifully distracting sunset in the phone picture above.
I spoke about the structural characterization (by "well-formed sequences") of claw-free monopolar graphs and the resulting polynomial-time recognition algorithm. It was based on the research I did in my last year of undergrad and was submitted as "The polarity and monopolarity of claw-free graphs."
ROSS CHURCHLEY, University of Victoria
Monopolar claw-free graphsA graph is called monopolar if its vertices can be partitioned into an independent set and a disjoint union of cliques. Monopolar graphs, which include all bipartite and split graphs, form an important subclass of the so-called polar graphs. We present a structural characterization of monopolar claw-free graphs which suggests a simple \(O(n^3)\) algorithm for their recognition. This contrasts with the NP-completeness of related recognition problems, including those for monopolar graphs in general and for polar claw-free graphs.
UVic Research Fair Poster
Picture of me taken by the LTC
This year, I participated in the UVic Learning and Teaching Centre's first annual Undergraduate Research Fair. My poster (below) is based on research supported by the LTC's Undergraduate Research Scholarship and submitted as "The polarity and monopolarity of claw-free graphs" (see Papers).
Click for a large, PDF version of the poster. More pictures of the Undergraduate Research Fair can be found on the Learning and Teaching Centre's flickr photostream.
The LTC photographer catches me talking philosophy
