As it so happens though, pigs do have something to do with math apart from performing calculations for audiences. The link comes through another holiday, Yellow Pigs Day! (celebrated July 17th. What do people do on this day? They eat yellow cake, exchange yellow pig gifts, sing songs and carols about yellow pigs, and think of properties of the number 17. That's an odd sounding festivities list, but with a little background information it will make a bit more sense. I am not sure when Yellow Pig Day was added to the holidays list, but its yellow pig origins can be traced back to the 1960's. Whichever year it actually was, two math students, Mike Spivak and David C. Kelly, were given the assignment of analyzing properties of the number 17. After spending some time mulling over the problem (mind you that 17 has many interesting properties), the two began to joke about a mythical yellow pig with 17 legs, 17 eyelashes (can't remember if it was on each eye or combined...), etc. From that period of hard work and yellow pig musings eventually evolved what we now celebrate as Yellow Pigs Day.
So that explains where the yellow pigs and 17's come from! Interesting huh? :-) This post would not be complete though without mentioning at least one property of 17. I have seen many long extensive lists of the properties of 17 (e.g. its arithmetic properties, its occurrence in architecture, its appearance in important dates and events,..etc.), but what I have not seen much of are the properties of 17 that relate to graph theory. In fact, I have only come across a few. The one that I will discuss here has to do with what are called Ramsey numbers.
It turns out that there is a whole area of combinatorics research referred to as Ramsey theory. One subcategory of Ramsey theory involves the aforementioned Ramsey numbers which in turn relate to colorings and cliques of complete graphs. At the most basic level this kind of problem can be stated in the following way:
What is the minimum number R(r,b) such that all complete graphs on R(r,b) vertices with edges colored red or blue contain a complete subgraph of r vertices with all red edges, or a complete subgraph of b vertices with all blue edges. The number R(r,b) is a Ramsey number.It has been proven that such a number exists.
The definition may at first be a little confusing, so the best way to understand it is by considering the following classic problem: show that at a party of 6 people there are 3 who all know each other or three who all don't know each other. Rephrased in graph theory terms the problem boils down to showing that any blue-red edge coloring of the complete graph K6 contains either a 3 cycle of blue edges (Remember that a 3-cycle is K3) or a 3 cycle of all red edges. This interesting factoid can be verified pretty quickly by experimenting a little with edge colorings on K6. As it also turns out, K6 is the minimum complete graph that satisfies this. Trying the same thing out on K5, K4, K3, K2 and K1 will yield nada. To again state things in graph theory lingo, this means that 6 is equal to the Ramsey number R(3, 3).
This idea of having a minimum number associated with 2 colorings and monochromatic subgraphs can be extended to three or more finite colors. In particular suppose that you have c colors and c integers n1, n2,...nc. The extended result says that there is a complete graph on R(n1,..,nc) vertices and c colors such that for some i between 1 and c there is a complete monochromatic subgraph of color i. The smallest number R(n1,...,nc) that satisfies this property for integers n1,..,nc and c colors is the associated multicolor Ramsey number.
And that my graphsters and graphistas is all of the background that you will need to understand this post. Phew! Let me now state a very special graph property involving the number 17. Ready.....(drum roll). Wait for it....and...Now!
R(3, 3, 3) = 17.
Virtual applause. :-D
As with all of the things that I write about I like to find out whenever I can when something was proven and by whom. I did a little bit of searching for the information behind R(3,3,3), and after some snooping through the internet found that the multicolor Ramsey number R(3,3,3) was originally found by Greenwood and Gleason in 1955. In addition to the result, what really strikes me as amazing is the way in which it was proven. Evidently Greenwood and Gleason used finite fields to prove their result. Finite fields and graph theory are not two subjects that I would immediately associate with each other. An unexpected surprise. Awesome!!!! :-D
P.S. Oink!
