Due Tuesday, March 13 at noon.

### Like this:

Like Loading...

*Related*

This entry was posted on March 1, 2007 at 4:33 pm and is filed under 117b, Homework. 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.

March 10, 2007 at 12:40 pm |

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.

March 11, 2007 at 4:23 am |

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?

March 11, 2007 at 5:09 am |

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…

March 11, 2007 at 12:26 pm |

Also, why can we take k >= 2n+1? I thought we had to prove this for ANY k and ANY n.

March 11, 2007 at 3:16 pm |

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.

March 12, 2007 at 6:42 am |

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).

March 12, 2007 at 6:47 am |

“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.