{"id":471,"date":"2007-07-16T20:47:18","date_gmt":"2007-07-16T20:47:18","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/07\/16\/order-from-chaos-using-graphs-ramsey-theory\/"},"modified":"2007-07-16T20:47:18","modified_gmt":"2007-07-16T20:47:18","slug":"order-from-chaos-using-graphs-ramsey-theory","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/07\/16\/order-from-chaos-using-graphs-ramsey-theory\/","title":{"rendered":"Order From Chaos Using Graphs: Ramsey Theory"},"content":{"rendered":"<p><img data-recalc-dims=\"1\" loading=\"lazy\" decoding=\"async\" alt=\"ramsey-triangle.jpg\" src=\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_204.jpg?resize=137%2C144\" width=\"137\" height=\"144\" class=\"inset right\" \/><br \/>\nOne application of graph theory that&#8217;s particularly interesting to me<br \/>\nis called Ramsey theory. It&#8217;s particularly interesting as someone who<br \/>\ndebunks a lot of creationist nonsense, because Ramsey theory is in<br \/>\ndirect opposition to some of the basic ideas used by bozos to<br \/>\npurportedly refute evolution. What Ramsey theory studies is when some<br \/>\nkind of ordered structure *must* appear, even in a pathologically<br \/>\nchaotic process. Ramsey theory is focused largely on *structures* that<br \/>\nexhibit particular properties, and those structures are usually<br \/>\nrepresented as graphs.<\/p>\n<p><!--more--><br \/>\nFor example, the most common introductory application of Ramsey theory<br \/>\nis to ask: given a complete graph K<sub>N<\/sub>.  What is the minimum<br \/>\nN for which you *cannot* assign a 2-coloring to its nodes without<br \/>\ngetting a single-colored triangle. The solution is 6: there is no possible assignment of two colors to edges in a complete graph without having at least one single-colored triangle.  This is, in fact, known as Ramsey&#8217;s theorem.<br \/>\nThere are a lot of other similar problems, which all have the flavor of looking at progressively larger structures, and asking how large the structure needs to grow before it *must* necessarily contain a particular substructure.<br \/>\nThere&#8217;s the clique theorem, which asks: given a graph with N nodes,<br \/>\nfor some number k&lt;N, how many edges can you add before the graph<br \/>\n*must* contain at least one k-clique?<br \/>\nA case where the underlying proof is graph theoretic, but the graph<br \/>\nisn&#8217;t completely obvious is the Hales-Jewett theorem. This says for any<br \/>\ntwo numbers N and C, there is a number H such that any assignment of C colors to the cells of an H-dimensional (N&times;N&times;N&times;&#8230;&times;N) cube<br \/>\n*must* contain at least one full row which has the same color. To see how<br \/>\nthis reduces to a graph problem, think of each cell of the cube as a vertex,<br \/>\nassigning colors to the vertices, and then looking for a certain kind of<br \/>\npath through nodes assigned the same color.<br \/>\nHales-Jewett is also sometimes called the tic-tac-toe theorem, because one<br \/>\nway of interpreting it is: H is the minimum dimensionality of a game of<br \/>\nN-in-a-row tic-tac-toe with C players where one player *must* win; the game cannot possibly end in a draw.<br \/>\nThe reason why this should be of particular interest in terms of the evolution debates should be obvious: the creationists like to make arguments of the form &#8220;X cannot happen, because order cannot arise from chaos&#8221;. Bzzzt. No, given a large enough disordered system, order *must* inevitably arise in some part of it. What Ramsey theory shows is that disorder, carried to a sufficiently high degree, is a kind of order in itself. In Ramsey proofs, in general, the only way to drag out a process to its Ramsey bound is by *deliberately* being adversarially<br \/>\nchaotic: doing things in a way that specifically delays the order as long as possible. Take K<sub>20<\/sub>, and assign a 2-coloring to its edges. Odds are, you&#8217;re going to get a single-colored triangle long before you&#8217;ve fully colored a subgraph isomorphic to K<sub>6<\/sub>; you have to deliberately work to avoid coloring a triangle before you&#8217;ve colored a subgraph of K<sub>6<\/sub>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>One application of graph theory that&#8217;s particularly interesting to me is called Ramsey theory. It&#8217;s particularly interesting as someone who debunks a lot of creationist nonsense, because Ramsey theory is in direct opposition to some of the basic ideas used by bozos to purportedly refute evolution. What Ramsey theory studies is when some kind of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","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":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[25],"tags":[],"class_list":["post-471","post","type-post","status-publish","format-standard","hentry","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-7B","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/471","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=471"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/471\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=471"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=471"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=471"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}