{"id":23147,"date":"2013-05-11T13:45:14","date_gmt":"2013-05-11T17:45:14","guid":{"rendered":"http:\/\/blogs.ams.org\/mathgradblog\/?p=23147"},"modified":"2014-07-10T14:32:45","modified_gmt":"2014-07-10T19:32:45","slug":"mathematics","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/mathgradblog\/2013\/05\/11\/mathematics\/","title":{"rendered":"Party At Ramsey’s"},"content":{"rendered":"

\"K6\"<\/a>“Why mathematics?” \u00a0is a question that greets me on occasion from friends and acquaintances wanting to delve into a casual conversation about the subject. \u00a0 Many times I will start out by offering a recreational math example, such as the Six Person Party Problem from Ramsey Graph Theory.\u00a0 \u00a0 This is a great problem to present, because, unlike other maths that deal with jargon such as Meromorphic Functions , Hermitian Operators ,(or insert your favorite years-to-understand abstract math term here), Ramsey Graph Theory, and a lot of related Graph Theory in general, can be approached in the beginning with a grasp of high school algebra and a little mathematical maturity.<\/p>\n

<\/p>\n

Basically,\u00a0 imagine yourself at a party with five other people.\u00a0 At this party\u00a0 there is either some three that are mutual friends or some three that are mutual strangers. \u00a0 This is always the case with a group of six or more people. \u00a0 \u00a0 One can easily prove this\u00a0\u00a0in an informal conversation style\u00a0by modeling the party with a graph.<\/p>\n

A graph in Graph Theory is not the same as a graph of some function f(x) that is usually seen in a course on calculus.\u00a0 Rather, it is a set of \u201cpoints\u201d (just as\u00a0 you would think of a dot on a piece of paper) that we call vertices or nodes and a set of edges (think straight line segments) such that every edge has two nodes, one at each end, and there is a\u00a0reflexive relation between the nodes and edges. \u00a0 This is a general definition of a classic graph.\u00a0 The nodes and edges can abstractly represent a great variety of relations.<\/p>\n

A complete graph is a graph such that every two nodes is connected via one edge. \u00a0Thus, a complete graph on six nodes (the nodes representing the six people) can be used to model our party.\u00a0 Now, if we pick one node, call it A,\u00a0 it is connected to the other five with five distinct edges by the given definition of a complete graph.\u00a0 Furthermore, if I take two crayons, red\u00a0 for friendship and blue for strangers, and started coloring at random each edge one of the two colors, then I will always get some three of the five that share the same color.\u00a0 This is an example of a powerful tool in combinatorics known as the Pigeonhole Principle.<\/p>\n

Pick the three edges that have the same color and let them all be red.\u00a0 Since the graph is a complete graph, the end nodes\u00a0B, C, and D,\u00a0of the three edges, are connected to A and to each other as well.\u00a0 Therefore, any two of B,C, and D with A form a triangle and B, C, and D forms a triangle by themselves also. Triangles in Graph Theory are the same as a complete graph with three nodes.<\/p>\n

If I start coloring the edges of the triangle formed by B, C, and D randomly red and blue, then an edge will be colored red, in which case there will be a\u00a0 red monochromatic triangle formed by A and the two end nodes of B,C, and D that share the common red edge.\u00a0 However, if we tried to avoid this and color all the edges of the triangle formed by B,C, and D blue, then we have a blue monochromatic triangle formed by the nodes B, C, and D. \u00a0A red monochromatic triangle represents three mutual friends and a\u00a0blue monochromatic triangle represents three mutual strangers. \u00a0Therefore, as you can see we have proved, using a graph as a model, that at a party of six or more people there always exists some three people who are mutual friends or mutual strangers.<\/p>\n

This property of always having a forced monochromatic triangle of one color or the other when coloring the edges randomly with two colors (known as 2-coloring) is not true for a complete graph with five nodes.\u00a0 Therefore, the minimum number of nodes needed to force a monochromatic triangle of one color or the other is six and is represented by the Ramsey notation R(3,3)=6, where R(k,k) is known as a Diagonal Ramsey Number. \u00a0 Using this notation, \u00a0mathematicians know that R(4,4)=18.\u00a0 But no one knows what R(5,5) or R(6,6) equals. \u00a0 It is not even feasible to computationally verify them.\u00a0 \u00a0 Do you know what they equal?\u00a0 A quick Google search will give you bounds for them and a plethora of technical results.\u00a0 \u00a0 It is problems like this that I believe help answer the opening question and bring us closer to understanding the beauty of mathematics.<\/p>\n

<\/div>","protected":false},"excerpt":{"rendered":"

“Why mathematics?” \u00a0is a question that greets me on occasion from friends and acquaintances wanting to delve into a casual conversation about the subject. \u00a0 Many times I will start out by offering a recreational math example, such as the … Continue reading →<\/span><\/a><\/p>\n

<\/div>\n","protected":false},"author":60,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3,8,1],"tags":[],"class_list":["post-23147","post","type-post","status-publish","format-standard","hentry","category-ams","category-general","category-uncategorized"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3gbww-61l","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/23147","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/users\/60"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/comments?post=23147"}],"version-history":[{"count":23,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/23147\/revisions"}],"predecessor-version":[{"id":24995,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/23147\/revisions\/24995"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/media?parent=23147"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/categories?post=23147"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/tags?post=23147"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}