End of YSP and other stuff
Jul. 27th, 2007 06:56 pmYeah, no good title for this one.
So today was the last day of YSP.
Perhaps Arunas's worst yet - he introduced groups - and groupoids - yesterday, on the second-to-last day. Today? Seifert-van Kampen! I'm going to guess at most 1 person actually understood what he was talking about, if any - well, more specifically, I'll guess nobody understood it. (And today there's no problem session wherein we can go over this stuff - not that we would if there were, as we've given up on following him.)
Also, at 11:30 today - right when class was supposed to end - he says, "I bet you're all wondering why I haven't introduced the quaternions yet." Actually, I think it's safe to say nobody was wondering that. Aside from the fact that probably none of the kids knew what quaternions were, none of us were wondering it either, as nothing he had been doing had hinted at quaternions. After about 5 minutes, we told him to wrap it up, we need to get downstairs, so he stops right where he is, says, "OK, the end," and draws a setting sun on the board.
And so later was the final evaluation meeting, and all us counselors complained about what Arunas had been doing, and it looks like he's going to keep on doing it, as he has all these years. (Though he admits this year may have been espeically bad.)
Meanwhile, Babai has returned from his weeklong absence to start a completely new series of lectures - transfinite combinatorics! Yay, cool stuff.
In particular - Erdös-deBruijn theorem - for finite k, a graph is k-colorable iff all its finite subgraphs are. Babai says it's a Zorn's Lemma proof, asks us how we would go about it. I try the obvious thing - take k-colorings of induced subgraphs, order by inclusion/extension. This satisfies the Zorn's Lemma condition, sure enough, but why must a maximal such be all of G? Uh... we try various things to prove this for a bit before Babai tells us, actually, he doesn't know of any way of proving the theorem this way. It's a Zorn's Lemma proof, but certainly not of the standard sort - instead, you consider supergraphs of G, on the same set of vertices, which also have the property that every finite subgraph is k-colorable. Zorn's Lemma lets you take a maximal such. You then prove that in such a graph, non-adjacency is transitive (this, of course, was left as an exercise), i.e. it's a complete l-partite graph for some l, and then your condition implies l≤k. Huh.
Also a graph-theoretic interpretation of the Borsuk-Ulam theorem, which I don't feel like writing up right now.
Another thing - Babai was proving that there are triangle-free graphs of arbitrarily large chromatic number (the generalization, that for any cardinal κ and whole number n, there's a graph G with Χ(G)≥κ and no odd cycles of length ≤n, was left as an exercise), and it so happened that this proof required that every set can be totally ordered. Not that every set can be well-ordered, just that every set could be totally ordered. This was something I had actually wondered about before - not really thought about, as I had no idea how to approach such a thing - about whether this could be proved without choice, or is equivalent, or whatever, and Babai, upon noticing that it does not require the full strength of well-ordering, wondered about this aloud. Turns out, the scribe for the class has actually studied this sort of set theory and reverse mathematics, and this is something people have worked on. Apparently it's unprovable in ZF, but strictly weaker than choice.
I fell compelled to mention James Albrecht's death[0], but I don't think there's really anything new I can say about it.
-Harry
[0]To abruptly change the tone of the entry...
So today was the last day of YSP.
Perhaps Arunas's worst yet - he introduced groups - and groupoids - yesterday, on the second-to-last day. Today? Seifert-van Kampen! I'm going to guess at most 1 person actually understood what he was talking about, if any - well, more specifically, I'll guess nobody understood it. (And today there's no problem session wherein we can go over this stuff - not that we would if there were, as we've given up on following him.)
Also, at 11:30 today - right when class was supposed to end - he says, "I bet you're all wondering why I haven't introduced the quaternions yet." Actually, I think it's safe to say nobody was wondering that. Aside from the fact that probably none of the kids knew what quaternions were, none of us were wondering it either, as nothing he had been doing had hinted at quaternions. After about 5 minutes, we told him to wrap it up, we need to get downstairs, so he stops right where he is, says, "OK, the end," and draws a setting sun on the board.
And so later was the final evaluation meeting, and all us counselors complained about what Arunas had been doing, and it looks like he's going to keep on doing it, as he has all these years. (Though he admits this year may have been espeically bad.)
Meanwhile, Babai has returned from his weeklong absence to start a completely new series of lectures - transfinite combinatorics! Yay, cool stuff.
In particular - Erdös-deBruijn theorem - for finite k, a graph is k-colorable iff all its finite subgraphs are. Babai says it's a Zorn's Lemma proof, asks us how we would go about it. I try the obvious thing - take k-colorings of induced subgraphs, order by inclusion/extension. This satisfies the Zorn's Lemma condition, sure enough, but why must a maximal such be all of G? Uh... we try various things to prove this for a bit before Babai tells us, actually, he doesn't know of any way of proving the theorem this way. It's a Zorn's Lemma proof, but certainly not of the standard sort - instead, you consider supergraphs of G, on the same set of vertices, which also have the property that every finite subgraph is k-colorable. Zorn's Lemma lets you take a maximal such. You then prove that in such a graph, non-adjacency is transitive (this, of course, was left as an exercise), i.e. it's a complete l-partite graph for some l, and then your condition implies l≤k. Huh.
Also a graph-theoretic interpretation of the Borsuk-Ulam theorem, which I don't feel like writing up right now.
Another thing - Babai was proving that there are triangle-free graphs of arbitrarily large chromatic number (the generalization, that for any cardinal κ and whole number n, there's a graph G with Χ(G)≥κ and no odd cycles of length ≤n, was left as an exercise), and it so happened that this proof required that every set can be totally ordered. Not that every set can be well-ordered, just that every set could be totally ordered. This was something I had actually wondered about before - not really thought about, as I had no idea how to approach such a thing - about whether this could be proved without choice, or is equivalent, or whatever, and Babai, upon noticing that it does not require the full strength of well-ordering, wondered about this aloud. Turns out, the scribe for the class has actually studied this sort of set theory and reverse mathematics, and this is something people have worked on. Apparently it's unprovable in ZF, but strictly weaker than choice.
I fell compelled to mention James Albrecht's death[0], but I don't think there's really anything new I can say about it.
-Harry
[0]To abruptly change the tone of the entry...
