{"id":657,"date":"2011-03-26T21:31:39","date_gmt":"2011-03-26T12:31:39","guid":{"rendered":"http:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/?p=657"},"modified":"2015-07-28T21:00:55","modified_gmt":"2015-07-28T12:00:55","slug":"2011kms","status":"publish","type":"post","link":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/","title":{"rendered":"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society"},"content":{"rendered":"<div class=\"talk\">Special Session on Graph Theory &#8211; <a href=\"http:\/\/www.kms.or.kr\/meetings\/spring2011\/home.htm\">2011 spring Meeting of the Korean Mathematical Society<\/a><\/div>\n<div class=\"date\">April 30, 2011, 9:00-11:40<\/div>\n<div class=\"talk\"><a href=\"http:\/\/newton.kias.re.kr\/KIAS-RIMS2006\/direction-koreaU.html\">Asan Science Building (\uc544\uc0b0\uc774\ud559\uad00)<\/a>, Korea University (\uace0\ub824\ub300), Seoul<\/div>\n<p><a href=\"http:\/\/www.kms.or.kr\/home\/kor\/symposium\/apply\/default.asp?mode=insert&amp;globalmenu=2&amp;localmenu=5\">Preregistration<\/a> deadline: April 11<\/p>\n<div class=\"talk\">Timetable<\/div>\n<ul>\n<li>9:00-9:30 <a href=\"http:\/\/mathsci.kaist.ac.kr\/~sangil\/\">Sang-il Oum<\/a> (\uc5c4\uc0c1\uc77c), \u00a0KAIST : Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices<\/li>\n<li>9:30-10:00 <a href=\"http:\/\/math.yu.ac.kr\/math\/sub01_b.htm\">Sejeong Bang (\ubc29\uc138\uc815)<\/a>, Yeungnam University :\u00a0Geometric distance-regular graphs with smallest eigenvalue -3<\/li>\n<li>10:00-10:10 Break<\/li>\n<li>10:10-11:40 <a href=\"http:\/\/webbuild.knu.ac.kr\/~mhs\/\">Mark H. Siggers<\/a>, Kyungpook National University :\u00a0The H-colouring Dichotomy through a projective property<\/li>\n<li>10:10-10:40 <a href=\"http:\/\/webbuild.knu.ac.kr\/~trj\/\">Tommy R. Jensen<\/a>, Kyungpook National University :\u00a0On second Hamilton circuits in cubic graphs<\/li>\n<li>11:10-11:40 <a href=\"http:\/\/math.postech.ac.kr\/~koolen\/\">Jack Koolen<\/a>, POSTECH :\u00a0Recent progress of distance-regular graphs<\/li>\n<\/ul>\n<p>Organized by <a href=\"http:\/\/home.konkuk.ac.kr\/~skim12\/\">Seog-Jin Kim<\/a> (Konkuk University) and Sang-il Oum (KAIST).<\/p>\n<p>At 14:00-14:40, there will be an <a href=\"http:\/\/www.kms.or.kr\/meetings\/spring2011\/InvitedSpeakers.htm\">invited talk<\/a> by Xuding Zhu, <em>Thue choice number of graphs<\/em>.<\/p>\n<hr \/>\n<div class=\"talk\">Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices<\/div>\n<div class=\"speaker\"><a href=\"URL\">Sang-il Oum (\uc5c4\uc0c1\uc77c)<\/a><br \/>\nDepartment of Mathematical Sciences, KAIST<\/div>\n<div class=\"abstract\">We prove that every infinite sequence\u00a0of skew-symmetric or symmetric matrices M<sub>1<\/sub>, M<sub>2<\/sub>, \u2026\u00a0over a fixed finite field\u00a0must have a pair M<sub>i<\/sub>, M<sub>j<\/sub> (i&lt;j) such that\u00a0that M<sub>i<\/sub> is isomorphic to a principal submatrix of the Schur complement of a nonsingular principal submatrix in M<sub>j<\/sub>,\u00a0if those matrices have bounded rank-width.\u00a0This generalizes three theorems on\u00a0well-quasi-ordering of graphs or matroids admitting good tree-like decompositions;\u00a0(1) Robertson and Seymour&#8217;s theorem for\u00a0graphs of bounded tree-width,\u00a0(2) Geelen, Gerards, and Whittle&#8217;s theorem\u00a0for matroids representable over a fixed finite field having bounded\u00a0branch-width,\u00a0and (3) Oum&#8217;s theorem for graphs of bounded rank-width with respect\u00a0to pivot-minors.<\/div>\n<hr \/>\n<div class=\"talk\">Geometric distance-regular graphs with smallest eigenvalue \u22123<\/div>\n<div class=\"speaker\"><a href=\"http:\/\/math.yu.ac.kr\/math\/sub01_b.htm\">Sejeong Bang (\ubc29\uc138\uc815)<\/a><br \/>\nDepartment of Mathematics, Yeungnam University<\/div>\n<div class=\"abstract\">A non-complete distance-regular graph\u00a0\u0393\u00a0is called geometric if there exists a set\u00a0C\u00a0of Delsarte cliques such that each edge of\u00a0\u0393\u00a0lies in a unique clique in\u00a0C. In this talk, we determine the non-complete distance-regular graphs satisfying\u00a0max{3,8(a<sub>1<\/sub>+1)\/3}&lt;k&lt;4a<sub>1<\/sub>+10\u22126c<sub>2<\/sub>.\u00a0To prove this result, we first show by considering non-existence of\u00a04-claws that any non-complete distance-regular graph satisfying\u00a0max{3,8(a<sub>1<\/sub>+1)\/3}&lt;k&lt;4a<sub>1<\/sub>+10\u22126c<sub>2<\/sub>\u00a0is a geometric distance-regular graph with smallest eigenvalue\u00a0\u22123. Moreover, we classify the geometric distance-regular graphs with smallest eigenvalue\u00a0\u22123. As an application,\u00a07\u00a0feasible intersection arrays are ruled out.<\/div>\n<hr \/>\n<div class=\"talk\">The H-colouring Dichotomy through a projective property<\/div>\n<div class=\"speaker\"><a href=\"http:\/\/webbuild.knu.ac.kr\/~mhs\/\">Mark H. Siggers<\/a><br \/>\nDepartment of Mathematics, Kyungpook National University<\/div>\n<div class=\"abstract\">The H-colouring Dichotomy of Hell and Nesetril, proved in 1990, is one of the most quoted results in the field of Graph Homomorphisms. It says that H-coloring, the problem of deciding if a given graph G admits an homomorphism to the fixed graph H, is NP-complete if H contains an odd cycle, and otherwise polynomial time solvable.<br \/>\nIn this talk we present a short new proof of this result, recently published, using a new projective property defined for homomorphisms of powers of a graph G onto a graph H.<\/div>\n<hr \/>\n<div class=\"talk\">On second Hamilton circuits in cubic graphs<\/div>\n<div class=\"speaker\"><a href=\"http:\/\/webbuild.knu.ac.kr\/~trj\/\">Tommy R. Jensen<\/a><br \/>\nDepartment of Mathematics, Kyungpook National University<\/div>\n<div class=\"abstract\">A classical theorem of Cedric Smith guarantees the existence of a second Hamilton circuit other than a given one in any hamiltonian cubic graph. It is an open problem in complexity theory whether the corresponding search problem is polynomially solvable. We observe that a search algorithm, implicit in Bill Tutte&#8217;s nonconstructive proof of Smith&#8217;s theorem, has exponential running time. We also mention two possible candidates for search algorithms with polynomial complexity.<\/div>\n<hr \/>\n<div class=\"talk\">Recent progress of distance-regular graphs<\/div>\n<div class=\"speaker\"><a href=\"http:\/\/math.postech.ac.kr\/~koolen\/\">Jack Koolen<\/a><br \/>\nDepartment of Mathematics, POSTECH<\/div>\n<div class=\"abstract\">I will talk about recent progress of distance-regular graphs.<\/div>\n<hr \/>\n<p>(Invited lecture at 2PM)<\/p>\n<div class=\"talk\">Thue choice number of graphs<\/div>\n<div class=\"speaker\"><a href=\"http:\/\/www.math.nsysu.edu.tw\/~zhu\/\">Xuding Zhu<\/a><br \/>\nInstitute of Mathematics, Zhejiang Normal University, Jinhua, China<\/div>\n<div class=\"abstract\">A sequence of even length is a repetition if the first half is identical to the second half. A sequence is said to contain a repetition if it has a subsequence which is a repetition. A classical result of Thue says that there is an infinite sequence on 3 symbols which contains no repetition. This result motivated many deep research and challenging problems. One graph concept related to this result is Thue-colouring. A Thue-colouring of a graph G is a mapping which assigns to each vertex of G a colour (a symbol) in such a way that the colour sequence of any path of G contains no repetition. The Thue-chromatic number of a graph is the minimum number of colours needed in a Thue-colouring of G. Thue&#8217;s result is equivalent to say that the infinite path has Thue-chromatic number 3. It is also known that the Thue-chromatic number of any tree is at most 4.<br \/>\nThue-choice number of a graph G is the list version of its Thue-chromatic number, which is the minimum integer k such that if each vertex of G is given k-permissible colours, then there is a Thue-colouring of G using a permissible colour for each vertex. This talk will survey some research related to Thue Theorem and will show that Thue-choice number of paths is at most 4 and Thue choice number of trees are unbounded.<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Special Session on Graph Theory &#8211; 2011 spring Meeting of the Korean Mathematical Society April 30, 2011, 9:00-11:40 Asan Science Building (\uc544\uc0b0\uc774\ud559\uad00), Korea University (\uace0\ub824\ub300), Seoul Preregistration deadline: April 11 Timetable 9:00-9:30 Sang-il Oum (\uc5c4\uc0c1\uc77c), \u00a0KAIST : Rank-width and well-quasi-ordering of skew-symmetric or symmetric matrices 9:30-10:00 Sejeong Bang (\ubc29\uc138\uc815), Yeungnam University :\u00a0Geometric distance-regular graphs with [&hellip;]<\/p>\n","protected":false},"author":2,"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_newsletter_tier_id":0,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[73,17],"tags":[33,34,38,75,47,44],"jetpack_publicize_connections":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v20.4 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society - KAIST Discrete Math Seminar<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"sangil\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/\",\"url\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/\",\"name\":\"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society - KAIST Discrete Math Seminar\",\"isPartOf\":{\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#website\"},\"datePublished\":\"2011-03-26T12:31:39+00:00\",\"dateModified\":\"2015-07-28T12:00:55+00:00\",\"author\":{\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/f328402c4c228a354a890e163f997d51\"},\"breadcrumb\":{\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#website\",\"url\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/\",\"name\":\"KAIST Discrete Math Seminar\",\"description\":\"Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/f328402c4c228a354a890e163f997d51\",\"name\":\"sangil\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/998709a7e98f0e5cf9072789c822bd9c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/998709a7e98f0e5cf9072789c822bd9c?s=96&d=mm&r=g\",\"caption\":\"sangil\"},\"sameAs\":[\"http:\/\/mathsci.kaist.ac.kr\/~sangil\/\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society - KAIST Discrete Math Seminar","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/","twitter_misc":{"Written by":"sangil","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/","url":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/","name":"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society - KAIST Discrete Math Seminar","isPartOf":{"@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#website"},"datePublished":"2011-03-26T12:31:39+00:00","dateModified":"2015-07-28T12:00:55+00:00","author":{"@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/f328402c4c228a354a890e163f997d51"},"breadcrumb":{"@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/2011kms\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/"},{"@type":"ListItem","position":2,"name":"Special session on graph theory, 2011 Spring Meeting of the Korean Mathematical Society"}]},{"@type":"WebSite","@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#website","url":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/","name":"KAIST Discrete Math Seminar","description":"Seminar series on discrete mathematics @ Dept. of Mathematical Sciences, KAIST.","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/f328402c4c228a354a890e163f997d51","name":"sangil","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/998709a7e98f0e5cf9072789c822bd9c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/998709a7e98f0e5cf9072789c822bd9c?s=96&d=mm&r=g","caption":"sangil"},"sameAs":["http:\/\/mathsci.kaist.ac.kr\/~sangil\/"]}]}},"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/s2YVJJ-2011kms","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/posts\/657"}],"collection":[{"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/comments?post=657"}],"version-history":[{"count":30,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/posts\/657\/revisions"}],"predecessor-version":[{"id":2067,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/posts\/657\/revisions\/2067"}],"wp:attachment":[{"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/media?parent=657"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/categories?post=657"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathsci.kaist.ac.kr\/~sangil\/seminar\/wp-json\/wp\/v2\/tags?post=657"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}