Loading Events

« All Events

  • This event has passed.
:

Florian Gut and Attila Joó, Large vertex-flames in uncountable digraphs

Wednesday, June 30, 2021 @ 5:00 PM - 6:00 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

Florian Gut
Department of Mathematics, University of Hamburg, Germany
Attila Joó
Department of Mathematics, University of Hamburg, Germany
https://www.math.uni-hamburg.de/home/joo/

The local connectivity  $ \kappa_D(r,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $r\rightarrow v $ paths in $ D $. A spanning subdigraph $ L $ of $ D $ with $  \kappa_L(r,v)=\kappa_D(r,v) $ for every $ v\in V-r $ must have at least $ \sum_{v\in V-r}\kappa_D(r,v) $ edges. It was shown by Lovász that, maybe surprisingly, this lower bound is sharp for every finite digraph. The optimality of an $ L $ can be captured by the following characterization: For every $ v\in V-r $ there is a system $ \mathcal{P}_v $ of internally disjoint $ r\rightarrow v $ paths in $ L $ covering all the ingoing edges of $ v $ in $ L $ such that one can choose from  each $ P\in \mathcal{P}_v $ either an edge or an internal vertex in such a way that the resulting set meets every $ r\rightarrow v $ path of $ D $. We prove that every digraph of size at most $ \aleph_1 $  admits such a spanning subdigraph $ L $. The question if this remains true for larger digraphs remains open.

Details

Date:
Wednesday, June 30, 2021
Time:
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:
,

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
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.