{"id":24269,"date":"2013-11-12T23:18:51","date_gmt":"2013-11-13T03:18:51","guid":{"rendered":"http:\/\/blogs.ams.org\/mathgradblog\/?p=24269"},"modified":"2014-06-21T10:57:11","modified_gmt":"2014-06-21T15:57:11","slug":"erdos-gyarfas-conjecture","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/mathgradblog\/2013\/11\/12\/erdos-gyarfas-conjecture\/","title":{"rendered":"The Erd\u0151s\u2013Gy\u00e1rf\u00e1s Conjecture"},"content":{"rendered":"

\"images<\/a>Curiosity is a guiding light down the dark corridors of mathematical wonderment. With each turn, enlightenment protrudes from the ruble of faulty understanding into the illumination of new knowledge. With this analogy in mind, mathematics can aptly be described as a field in which a pencil, paper, and rational thought are employed to explore the connections and patterns embedded in the framework of algebraic and geometric abstractions. Theorem after theorem reveals the vast collection of mathematical discovery as well as the limitations of our current knowledge.<\/p>\n

Therefore, it becomes apparent that epistemology provides a foundation for the mathematically curious to trudge. For instance, in the field of combinatorics, theory depends on what is known about countable discrete structures. One such structure can be found in the concept of a simple graph. In essence, a simple graph \"G\" is a set of vertices and a set of edges (each with two ends) in which every edge has two vertices, exactly one at each end. As an example, a square is a simple graph in which the vertices are represented by the right angles where the edges meet.<\/p>\n

If there is a connected simple graph with \"n\" vertices, a cycle of length \"n\" can be defined by starting at the \"n\"th vertex and traveling to the other \"n-1\" vertices once and only once and returning to \"n\"th vertex. Suppose further, that there is one edge \"e\" and a vertex \"v\". If \"v\" is an end vertex of \"e\", then it is said that \"e\" is incident to \"v\". Moreover, the degree of a vertex \"v\", denoted \"deg(v)\", is the number of edges incident to \"v\". The minimum degree of a graph is the number of edges incident to the vertex with minimum degree. In the example of the square, each vertex has degree 2. So, the minimum degree of the square (which is a cycle of length four) is 2.<\/p>\n

One such open problem that deals with cycles and degrees in graphs is the Erd\u0151s\u2013Gy\u00e1rf\u00e1s Conjecture, proposed in 1995 by mathematicians Paul Erd\u0151s and Andr\u00e1s Gy\u00e1rf\u00e1s. The formal statement is as follows:<\/p>\n

The Erd\u0151s\u2013Gy\u00e1rf\u00e1s Conjecture:<\/strong> Every graph with minimum degree 3 contains a simple cycle whose length is a power of 2.<\/p>\n

A stronger version would be to prove the conjecture true for every cubic graph. \u00a0That is, for every graph in which every vertex is of degree 3. If a counterexample is to be constructed, the resultant graph would have at least 17 vertices as verified by computation. \u00a0 A quick internet search will yield a brief summary of the current research and computational results. \u00a0 How would you construct a counterexample or proof? \u00a0It only takes a little curiosity to light the way.<\/p>\n

 <\/p>\n

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

Curiosity is a guiding light down the dark corridors of mathematical wonderment. With each turn, enlightenment protrudes from the ruble of faulty understanding into the illumination of new knowledge. With this analogy in mind, mathematics can aptly be described as … 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,12,14,15,16,1],"tags":[],"class_list":["post-24269","post","type-post","status-publish","format-standard","hentry","category-ams","category-math","category-math-in-pop-culture","category-mathematics-in-society","category-mathematics-online","category-uncategorized"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3gbww-6jr","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/24269","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=24269"}],"version-history":[{"count":12,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/24269\/revisions"}],"predecessor-version":[{"id":24904,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/24269\/revisions\/24904"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/media?parent=24269"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/categories?post=24269"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/tags?post=24269"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}