Florian Gut and Attila Joó gave an online talk on the existence of a large vertex flame in every rooted directed graph of size ℵ_1 at the Virtual Discrete Math Colloquium

On June 30, 2021, Florian Gut and Attila Joó (University of Hamburg) gave an online talk at the Virtual Discrete Math Colloquium on their new result proving that every rooted directed graph of size $\aleph_1$ has a large vertex flame. The title of their talk was “Large vertex-flames in uncountable digraphs“.

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

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.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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