A better yodeling contest

Mathematics is supposed to be fun.

Somehow this often gets lost in the over-wrought verbiage, dry explanation and royal "we". One reason I chose to come to Calgary to work with Dr. Guy is he often does without all that, unmasking the enjoyment at the heart of it.

So, today I presented the "book proof" of Dinitz' Problem. "Book proof" because Erdös was involved briefly with it, and Erdös once said that the best proofs were kept in a thick leatherbound book on God's nightstand. Every once in a while, someone would be blessed to discover a proof of such beauty and insight that it could only have come from "the book".

(Erdös meant this metaphorically; he was not a theist.)

The pure math graduate students have been presenting these "proofs from the book" to each other every Tuesday, under the guidance of the head of the department. Today was my turn; I chose the Dinitz problem because it had a very colorful proof and was tangentially related to some of the things I am working on now.

It is not only the proof that is colorful; the problem is actually about colorings of a square matrix. Suppose there is a $n\times n$ square matrix, and each cell of the matrix is associated with a set of $n$ colors - where not all color sets are necessarily the same. Is it always possible to pick a color for each cell from its color set so no color appears twice in the same row or column? It turns out the answer is "yes".

The proof is actually quite simple, consisting simply of putting together two older lemmas in graph theory. The one which leads into the finale of the proof is the "stable matching" lemma. This is understood most easily as follows: given some men and women, there is some way of marrying them off so that no couple prefer each other to their current partners.

This lends itself readily to humor.

The kicker is that applying this lemma back to the matrix, it turns out that rows are represented by men, and the columns by women. So, I drew a big stick figure of a man on the "Y-axis", and a stick figure of a woman on the "X-axis". "For the obvious reasons," I said, and then added the symbol "X" before the names of these axes.

By this point of the proof, the square has been numbered according to a Latin square. There are arrows from smaller to larger numbers in each row, and numbers from larger to smaller in each column. So, interpreting this according to the stable matching lemma, we have:

"Men prefer smaller, women prefer larger."

There isn't really way around stating the adolescent double-entendre without making the proof duller or harder to understand. Besides,

Mathematics is supposed to be fun.

So, I left it in. I had a back-up explanation if necessary: that the men are providing gifts to the women. Women prefer larger gifts, while the men prefer to give the smallest gifts they can get away with.

Most people seemed to think it was funny.

I was even ready for some of the expected questions, like what would happen if some people preferred others of the same sex. The beautiful thing is that this leads directly into an open conjecture! You no longer necessarily have stable matchings, but the generalization of the Dinitz problem still seems to be true!

Nobody asked.

Fortunately.

The head of the department came back afterwards and warned me that I was coming too close to "crossing a line", and that I should be more careful. I suddenly realized that I had got myself into a bit of trouble. The other students present noted that he seemed to be getting even grumpier lately.

After some reflection, I realize that this is actually somewhat of an improvement over my past conversations with the department head, most of which consisted of him asking me "Who are you?" and "What are you doing here?" even after I have been here for more than a year. I wonder if this upward trend will continue.

Anyway, now it is time for me to return to completing my PhD application. I don't know who ends up reading that.

This entry was posted on Tuesday, January 30th, 2007 at 7.23 pm and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.