117b – Homework 8

Due Tuesday, March 13 at noon.

Homework 8

Advertisements

7 Responses to 117b – Homework 8

  1. Jed says:

    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.

  2. Domenic says:

    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?

  3. Domenic says:

    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…

  4. Domenic says:

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

  5. Jed says:

    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.

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: