{"id":4613,"date":"2022-03-10T01:25:52","date_gmt":"2022-03-10T06:25:52","guid":{"rendered":"http:\/\/matroidunion.org\/?p=4613"},"modified":"2022-03-21T04:11:10","modified_gmt":"2022-03-21T08:11:10","slug":"online-talk-ahmad-abdi-2","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=4613","title":{"rendered":"Online Talk: Ahmad Abdi"},"content":{"rendered":"\n<p><strong>Tuesday, March 15,<\/strong> <strong>3pm ET<\/strong> (*7pm* GMT, *8am* Wed NZDT)<br \/><strong><a href=\"https:\/\/www.lse.ac.uk\/Mathematics\/people\/Ahmad-Abdi\">Ahmad Abdi<\/a><\/strong>, LSE<br \/><strong>On packing dijoins in digraphs and weighted digraphs<\/strong><\/p>\n<div><strong>YouTube: <\/strong><a href=\"https:\/\/youtu.be\/MF1kVJ1V9Gk\">https:\/\/youtu.be\/MF1kVJ1V9Gk<\/a><\/div>\n<h5>\u00a0<\/h5>\n<h5><strong>Abstract:<\/strong><\/h5>\n<h5>Let $D=(V,A)$ be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes $D$ strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least $k$.<\/h5>\n<h5>\u00a0<\/h5>\n<h5>Woodall\u2019s Conjecture, an important open question in Combinatorial Optimization, states that there exist $k$ pairwise disjoint dijoins. We make a step towards resolving this conjecture by proving that $A$ can be decomposed into two sets $A_1$ and $A_2$, where $A_1$ is a dijoin, and $A_2$ intersects every dicut in at least $k-1$ arcs. We prove this by a Decompose, Lift, and Reduce (DLR) procedure, in which $D$ is turned into a sink-regular $(k,k+1)$-bipartite digraph. From there, by an application of Matroid Optimization tools, we prove the result.<\/h5>\n<h5>\u00a0<\/h5>\n<h5>The DLR procedure works more generally for weighted digraphs, and exposes an intriguing number-theoretic aspect of Woodall\u2019s Conjecture. In fact, under natural number-theoretic conditions, Woodall\u2019s Conjecture and a weighted extension of it are true. By pushing the barrier here, we expose strong base orderability as a key notion for tackling Woodall\u2019s Conjecture.<\/h5>\n<h5>\u00a0<\/h5>\n<h5>Based on joint work with Gerard Cornuejols and Michael Zlatin.<\/h5>\n","protected":false},"excerpt":{"rendered":"<p>Tuesday, March 15, 3pm ET (*7pm* GMT, *8am* Wed NZDT)Ahmad Abdi, LSEOn packing dijoins in digraphs and weighted digraphs YouTube: https:\/\/youtu.be\/MF1kVJ1V9Gk \u00a0 Abstract: Let $D=(V,A)$ be a digraph. A dicut is the set of arcs in a cut where all &hellip; <a href=\"https:\/\/matroidunion.org\/?p=4613\">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-4613","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\/4613","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=4613"}],"version-history":[{"count":3,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4613\/revisions"}],"predecessor-version":[{"id":4629,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4613\/revisions\/4629"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}