Due Tuesday, March 13 at noon.
Due Tuesday, March 13 at noon.
This entry was posted on Thursday, March 1st, 2007 at 4:33 pm and is filed under 117b: Computability theory. 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.
On page 3, Definition 1.6 and 1.9 seems to have the role of k and n switched–is this intentional or a mistake?
I can see it both ways, and I can probably think about the hint for Problem 1 more and figure out what these notation mean, but I am a bit confused right now, so I thought I would just ask here.
That would definitely make more sense, as I’m trying to work through the hint on 1 and getting essentially that (since k >= 2n + 1) “given a graph of size 2n+1, there is a monochromatic subgraph of size >= 3n+1.” I guess that works when n = 0 and k = 2n+1.
Wait, no, but switching them makes the homogeneity definition break… with the switching, this is what I get.
f : {1, …, w}^[k+n] –> {1, …, e + 2}
But |H| = 2n + 1.
Since H’s homogeneity refers to the size of the sets in the domain of f, we then have that “for all A, B in H^[k+n]”… but there are no subsets of H of size k + n (unless, again, n = 0 and k = 2n+1).
—-
I’m rather confused in general, actually, about the translation from the notation to words. Let’s try Ramsey’s theorem in words… (assume all graphs are connected)
“for all ???s k and subgraph sizes n, and all finite sets of colors C, there is a minimum graph size M such that for all graphs X of size >= M and all colorings f, some subgraph of H of size >= n will be colored the same way twice?”
That’s all wrong. Help anyone?
I think it might make more sense if we’re dealing with hypergraphs? Here’s what I have now…
“For all n and k >=1, and all finite sets of colors C, there is a M such that for all graphs X of size at least M and all colorings f that assign k edges in X to a color in C, there is a subgraph H of size at least n in X such that all k-sized subgraphs of H have the same coloring.”
The coloring doesn’t make much sense unless we can assign each edge multiple colorings…
Also, why can we take k >= 2n+1? I thought we had to prove this for ANY k and ANY n.
Regarding why we can take k >= 2n+1: I think if we proved that there is a set H in N^[k] of diagonal indiscernibles, then a subset of H also works.
Hi. Sorry for not having seen these before. Hmm… In the hint I want 2n+1 to be the size of the tuples the coloring is defined on and k+n (or w) to be the size of the homogeneous object. So: the superindex indicates the sizes of the tuples being colored, the number in parentheses indicates the size of the (min)-homogeneous object. The switch was an unfortunate typo on Definition 1.9.
Let’s see… Ramsey: Let’s say a k-hypergraph is a set A together with a relation on k-subsets of A (k-edges). So a (non-directed) graph (without loops) is just a 2-hypergraph. Is this the usual notation? The size of such a beast is the number of vertices, |A|. It is complete iff each k-edge is in the relation. Then Ramsey’s result becomes: “For all n and k >=1, and all finite sets of colors C, there is an M such that given any coloring f that assigns to each k-edge of the complete k-hypergraph of size M a color in C there is a complete (sub)-k-hypergraph H of size at least n such that all its k-edges have the same coloring.”
For k=2 and 2 colors this can be said in an easier way: For all a there is b such that any (non-directed, without loops) graph in at least b vertices either contains a complete subgraph of size a or an empty subgraph of size a. (Empty meaning there are no edges between the vertices).
“Also, why can we take k >= 2n+1? I thought we had to prove this for ANY k and ANY n.”
If we have a homogeneous (or min-homogeneous) set of size 20, then certainly we have one of size 4. So: If we prove that for all colorings of n-edges we obtain a (min)homogeneous object of size a+2n+1 then we have certainly obtained one of size at least a, so we may as well assume that a is at least 2n+1. Also using the same idea, given any number z we may as well assume that the least number in the homogeneous set is at least z, since it suffices to obtain a homogeneous set of size z+a to ensure we have a homogeneous set of size a whose least element is at least z.