RT Part 3; Hypergraphs and Other Generalizations

Before we move onto colorings of \mathbb{N}, I thought I’d say one more thing about the generalization of our previous results to hypergraphs and one example of it in action.  This will take two posts.  In this post I wanted to talk about another generalization of our coloring scheme from last time and introduce hypergraphs, all to dramatically set up the next post.

Last time we showed that for any natural numbers n and k, there exists some other natural number N such that however the complete graph K_N is k-colored, there always exists a monochromatic complete graph of size n.  So if our colors are labeled by 1,2, ... , k, then said slightly differently, N is big enough to guarantee either a monochromatic K_n of color 1, or a monochromatic K_n of color 2, … , or a monochromatic K_n of color k.

A natural generalization of this is: Given natural numbers k, p_1, p_2, ... , p_k, there also exists some N such that however K_N is k-colored we are guaranteed either a monochromatic K_{p_1} of color 1, a monochromatic K_{p_2} of color 2, … , or a monochromatic K_{p_k} of color k.  So we are more demanding for certain colors.  Note that by letting n = \max\{p_1, p_1, ... , p_n\} this statement follows directly from the previous one.

And, as I asserted last time, this holds for hypergraphs too.  But what is a hypergraph?  Well, a regular old graph can be viewed as a set of vertices  and a set of edges where each edge is a pair of vertices.  A hypergraph is exactly the same except the word “pair” is now unrestricted.  Meaning a (hyper)edge can be triple of vertices, or a quadruple, or any other (for now) finite number of vertices.

Alternatively, I could have defined a hypergraph the way my professor Jacques Verstraete at UCSD did:  “Now I am going to define what a hypergraph is.  Everything.  Everything is a hypergraph.  (pause for laughter)  I am a hypergraph.  You are a hypergraph.  This room, the chalkboard, and the desks are a hypergraph.  That’s because any collection of sets forms a hypergraph.”

For example, this is a picture of a hypergraph which I stole from Wikipedia and am republishing (assuming that’s legal) or which I drew myself and coincidentally looks much like Wikipedia’s (if it’s not).

This hypergraph has 7 vertices and 4 hyperedges.  The hyperedge e_1 contains 3 vertices, the hyperedge e_2 contains two and is actually contained properly within e_1.  e_3 contains 3 vertices and e_4 one.

A $k$-uniform hypergraph is one where each edge consists of exactly k vertices.  And just like in the graph case, a complete k-uniform hypergraph on N vertices is a k-uniform hypergraph where every collection of k vertices forms an edge.

Ok, so we asserted last time that our boring-in-comparison results can be generalized from graphs to everything (i.e. to hypergraphs).  Let’s state one such theorem, sometimes called Ramsey’s Theorem.  It deals with colorings of complete, k-uniform hypergraphs.

Theorem.  Given natural numbers k, r, p_1, p_2, ... , p_k, there exists an N such that any k-coloring of the hyperedges of the complete r-uniform hypergraph on N vertices contains either p_1 vertices all of whose r-hyperedges (i.e. all subsets of size r) were given the color 1, or there are p_2 vertices all of whose hyperedges are color 2, or … , or there are p_k vertices all of whose hyperedges are color k.

Of course the “or” is a non-exclusive or.  Many could happen.  Let’s write the smallest N in the previous theorem that does the job N = R(p_1, p_2, ... , p_k, r).  One proof of this result is by induction on r, the degree of uniformity.  If r=2 then all the edges have size two and we are in the regular graph case for which we know it holds.  In the way Doug West proves it in his book, the inductive step is somewhat complicated.  For one, the inductive step is itself a proof by induction.  And he even (for clarity) only proves this explicitly for the case k=2.  It’s confusing enough, and more fiddly than clever, that we’ll skip it.

Next time we will see an application of result.  (Note: I of course mean an application to another problem in pure math.  Sorry NSF, that’s really what we care about.)

Advertisements

About Jay Cummings

I am a fifth year mathematics Ph.D. student at UCSD.
This entry was posted in Ramsey Theory. Bookmark the permalink.

12 Responses to RT Part 3; Hypergraphs and Other Generalizations

  1. Z Norwood says:

    I always thought the number of vertices in a hyper-edge had to be constant in a hypergraph. (So 2-hypergraphs would be graphs, 3-hypergraphs would be sets of triples of a set, etc.) Guess I was wrong!

  2. JCummings says:

    O no, dogg. Everything means everything! The lack of restrictions probably makes some of the problems closer to legit set theory problems. Although as far as I know the questions usually asked are just generalizations of the standard graph theory problems. Measuring the standard invariants, etc. But you might like it!

  3. soffer801 says:

    Yup. If they are all the same, we call it uniform (kind of like regularity for graphs)

    A nonmathematical problem was once posed to me that I was sure had a Ramsey-esque solution:

    Find 3 foods which do not taste good together, but if you removed any one, the remaining pair would taste good together. Here we are two-coloring the edges of a complete 2-uniform hypergraph and 3-uniform hypergraphs and looking for a specific subgraph. Unfortunately, Ramsey says nothing about non-uniform hypergraphs.

    • JCummings says:

      Ramsey says nothing about non-uniform hypergraphs? What do you mean? I don’t know of an example off hand, but what invalidates the other hypergraphs from Ramsey theory? For instance, the k-regular hypergraph case (each vertex is in exactly k edges) seems like it could have some Ramsey results. Or other subsets of hypergraphs or hypergraphs in general, I would think.

  4. Z Norwood says:

    Great pictures again!

    If you (Jay and any Mac-user) are still using MetaPost and still using TeXShop, copy the files nv-metafun.engine and nv-metapost.engine from ~/Library/TeXShop/Engines/Inactive/MetaPost to ~/Library/TeXShop/Engines (and check out the Readme in …/MetaPost), as instructed in the document you’ll find by clicking Help > About this Release in TeXShop. Before you do this, though, be sure to get the latest release of TeXLive here (and therewith the latest release of TeXShop (I lied: You have to download TeXShop v3.xx after installing MacTeX 2011.)). These engines are supposed to be loads better than the default TeXShop engines.

  5. Danny Sabra says:

    dude, your blog is intense! yet, i insist on reading every single post.

    • Z Norwood says:

      Excellent! I hope your long-dormant desire to do mathematics is resurfacing.

      Or maybe this will inspire you to do a violin blog?

      • Danny Sabra says:

        God help us all if I did a violin blog. Back in my school days (last year) I could’ve done a mean music theory blog. or something along those lines, which might not be too far off of some of the math here. I composed a piece a while back using the Infinity Series which was a lot of fun. But I’m afraid most of this stuff is above my pay grade.

  6. JCummings says:

    Thanks Zach! I will definitely check them out!

    And thanks Danny! We’re just getting going but are really enjoying it so far. Sometime soon a couple more bloggers may join up who have other cool interests. Feel free to “follow” the blog to get notified when new stuff is posted. :-)

  7. Pingback: RT Part 4; The Happy Ending Theorem | whateversuitsyourboat

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