Zoltan Szigeti - Evolution of arborescence packing

27 mai 25

Speaker: Zoltan Szigeti

Title:  Evolution of arborescence packing

Room: D209

Date: 27/05/2025 14:00

Abstract:

 

I will present a general result on packing arborescences, namely the characterization of the existence of an ''h-regular M-independent-rooted (f, g)-bounded (α, β)-limited packing of mixed hyperarborescences’’. 

 

The problem can be described as follows: we are given a mixed hypergraph F and a matroid M on its vertex set; we want to decide whether there exists a set B of mixed hyperarborescences in F such that 

  1. the mixed hyperarborescences in B are hyperedge and hyperarc disjoint,

  2. each vertex of F is a head or the root in h mixed hyperarborescences in B,

  3. the roots of the mixed hyperarborescences in B form an independent set in the matroid M,

  4. the number of mixed v-hyperarborescences in B is at least f(v) and at most g(v) for every vertex v of F,

  5. the number of the mixed hyperarborescences in B is at least α and at most β.

This result provides a common generalization of a great number of earlier results on packing arborescences:

  1. Edmonds: packing of k spanning arborescences with fixed roots,

  2. Frank: packing of k spanning arborescences with flexible roots,

  3. Frank, Cai: (f,g)-bounded packing of k spanning arborescences,

  4. Frank: packing of k spanning mixed arborescences with fixed roots,

  5. Gao, Yang: packing of k spanning mixed arborescences with flexible roots,

  6. Frank, Király, Király: packing of k spanning hyperarborescences with fixed roots,

  7. Fortier, Király, Léonard, Szigeti, Talon: packing of k spanning mixed hyperarborescences with fixed roots,

  8. Hörsch, Szigeti: (f,g)-bounded packing of k spanning mixed hyperarborescences,

  9. Bérczi, Frank: h-regular (f, g)-bounded (α, β)-limited packing of arborescences,

  10. Szigeti: h-regular (f, g)-bounded (α, β)-limited packing of mixed hyperarborescences,

  11. Szigeti: h-regular M-basis-rooted (f, g)-bounded packing of mixed arborescences,

  12. Gao+Szigeti: h-regular M-basis-rooted (f, g)-bounded packing of mixed hyperarborescences.