{"id":4622,"date":"2022-03-17T00:51:07","date_gmt":"2022-03-17T04:51:07","guid":{"rendered":"http:\/\/matroidunion.org\/?p=4622"},"modified":"2022-03-29T01:56:32","modified_gmt":"2022-03-29T05:56:32","slug":"online-talk-o-joung-kwon","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=4622","title":{"rendered":"Online Talk: O-joung Kwon"},"content":{"rendered":"\n<p><strong>Tuesday, March 22,<\/strong> <strong>5pm ET<\/strong> (*9pm* GMT, *10am* Wed NZDT)<br \/><strong><a href=\"http:\/\/ojkwon.com\/?ckattempt=1\">O-joung Kwon<\/a><\/strong>, Hanyang University<br \/><strong>Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)<\/strong><\/p>\n<div><strong>YouTube: <\/strong><a href=\"https:\/\/youtu.be\/GV-xsK3xtxY\">https:\/\/youtu.be\/GV-xsK3xtxY<\/a><\/div>\n<h5>\u00a0<\/h5>\n<h5><strong>Abstract: <\/strong><\/h5>\n<h5>In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomass\u00e9 and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. Furthermore, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6. This is joint work with \u00c9douard Bonnet and David Wood.<\/h5>\n<p>\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tuesday, March 22, 5pm ET (*9pm* GMT, *10am* Wed NZDT)O-joung Kwon, Hanyang UniversityReduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond) YouTube: https:\/\/youtu.be\/GV-xsK3xtxY \u00a0 Abstract: In a reduction sequence of a graph, vertices are successively identified until &hellip; <a href=\"https:\/\/matroidunion.org\/?p=4622\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11],"class_list":["post-4622","post","type-post","status-publish","format-standard","hentry","category-matroids","tag-online-talks"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4622","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4622"}],"version-history":[{"count":3,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4622\/revisions"}],"predecessor-version":[{"id":4635,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4622\/revisions\/4635"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4622"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4622"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4622"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}