Before we move onto colorings of , 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 and , there exists some other natural number such that however the complete graph is -colored, there always exists a monochromatic complete graph of size . So if our colors are labeled by then said slightly differently, is big enough to guarantee either a monochromatic of color 1, or a monochromatic of color 2, … , or a monochromatic of color .
A natural generalization of this is: Given natural numbers , there also exists some such that however is -colored we are guaranteed either a monochromatic of color 1, a monochromatic of color 2, … , or a monochromatic of color . So we are more demanding for certain colors. Note that by letting 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 contains 3 vertices, the hyperedge contains two and is actually contained properly within . contains 3 vertices and one.
A $k$-uniform hypergraph is one where each edge consists of exactly vertices. And just like in the graph case, a complete -uniform hypergraph on vertices is a -uniform hypergraph where every collection of 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, -uniform hypergraphs.
Theorem. Given natural numbers , there exists an such that any -coloring of the hyperedges of the complete uniform hypergraph on vertices contains either vertices all of whose hyperedges (i.e. all subsets of size ) were given the color , or there are vertices all of whose hyperedges are color , or … , or there are vertices all of whose hyperedges are color .
Of course the “or” is a non-exclusive or. Many could happen. Let’s write the smallest in the previous theorem that does the job . One proof of this result is by induction on , the degree of uniformity. If 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 . 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.)