Graphs, Ramsey Numbers

Ramsey Numbers

given a party of 6 people, show that 3 are mutual acquaintences or 3 are mutual strangers.

Select any one of the six party guests.  He either knows, or does not know, 3 others.  If he knows them, and any pair of these three knows each other then he joins this pair in an acquaintence triangle.  Otherwise his three acquaintences are mutual strangers.  The reasoning is the same if he doesn't know three people.

Ramsey (biography) generalized this simple party game, and developed the concept of a ramsy number.  The ramsey number ram(m,n) is the smallest integer, such that any graph incorporating that many vertices contains Km or -Kn.  In other words, a graph on that many points includes a complete graph on m points, or its complement includes a complete graph on n points.  Refering to the puzzel above, ram(3,3) = 6.  Given 6 people, 3 will know each other, a triangle in the graph, or three will be strangers, a triangle in the complement of the graph.  Verify that ram(2,n) = n, and ram(m,n) = ram(n,m).

Another incarnation of ramsey graph theory places edges between all vertices, and colors these edges red or blue.  In the earlier 6-person party problem, red might indicate an acquaintence while blue indicates a stranger.  However this version can be generalized to multiple colors, whereas the presence or absence of edges cannot.  In this context, ram(m,n) is the fewest number of vertices that will guarantee a monochrome subgraph Km, no matter how the edges are colored (using n colors).  Thus ram(3,2) = 6.

Warning, the following is a detour through transfinite ordinals, and not essential for the rest of graph theory.  You can skip it if you wish.

Let an infinite ordered set of vertices v have cardinality s.  Let a v cross v relation e join pairs of vertices, using edges that are either red or blue.  The first vertex v0 has red degree = s, or blue degree = s, or both.  Assume its red degree is s.  Restrict v (and hence e) to those vertices that join v0 through red edges.  Then choose the least vi in the resulting subgraph that has red degree = s.  Restrict v to those vertices that join vi through red edges.  Now every vertex joins v0 and vi through red edges.  Continue using transfinite induction.  If this process builds a subset of v having size s then we have found a complete red subgraph of size s, and we are done.  So assume the process terminates below vx.  In other words, for all ordinals y beyond x, vy has a red degree < s, and hence a blue degree = s.  Throw out all vertices below x, so that each vertex has blue degree = s and red degree < s.  As we attempted to do for red, we now do (successfully) for blue.  Restrict to the vertices that join v0 through blue edges, renumber vertices, restrict to vertices that join v1 in blue edges, renumber, and so on using transfinite induction.  Each step restricts to a subgraph by throwing out a set of vertices with cardinality < s.  Therefore the remaining subgraph always has size s, and we can continue until we finally build a complete blue subgraph of size s.

If we were faced with red, blue, and green edges, we would first attempt to find a complete red subgraph as before.  Failing this, we have produced a subgraph of size s such that each vertex has red degree < s.  Assuming the first vertex has blue degree = s, try to find a complete blue subgraph, and failing this, we are left with a subgraph of size s, where each vertex has green degree s and red and blue degrees < s.  Now we can build a complete green subgraph.  This works for finitely many colors, hence ram(s,n) = s.

If we have infinitely many colors, and we repeat the above process infinitely often, and never build a complete monochrome graph, we find a chain of subgraphs, each having cardinality s, whose intersection is empty.  Yet each subgraph has a vertex with least ordinal, giving a countable chain of ordinals below s, and approaching s, which is impossible if s is uncountable.  Therefore ram(s,t) = s when s is uncountable and t is coutable.  In general, ram(s,t) = s for any t < s.  Use transfinite induction on t.

Note that the same quantity of colors and vertices (s = t) guarantees no monochrome subgraphs at all.  Assign the edge vi→vj the color i, where i < j.