Loading Events

« All Events

  • This event has passed.
:

Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs

Tuesday, April 7, 2020 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Pascal Gollin
IBS Discrete Mathematics Group
https://dimag.ibs.re.kr/home/gollin/

A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins.

Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.
We study a modification of this question where we restrict our attention to certain classes of dibonds, i.e. whether for a class $\mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $\mathfrak{B}$ equal the size a minimum dibond in $\mathfrak{B}$.

In particular, we verify this questions for nested classes of dibonds, for the class of dibonds of minimum size, and for classes of infinite dibonds.

Details

Date:
Tuesday, April 7, 2020
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
Website:
https://dimag.ibs.re.kr/home/sangil/
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.