Some Erdős-Pósa type results

Speaker: Henning Bruhn-Fujimoto (Universität Ulm)

Abstract: There is often a dichotomy between packing and covering in graphs: either there are many disjoint A-B paths (packing) or few vertices suffice to hit all A-B paths (covering); either there are many disjoint cycles or a small vertex set meeting all cycles; either there are many edge-disjoint K_4-subdivisions or a small edge-set that meets every K_4-subdivision. If there is such a dichotomy for a class of hypergraphs, then it is said to have the Erdős-Pósa property.

For example the paths in Menger's theorems, cycles that meet at least one vertex from a fixed set, or K_4-subdivisions that meet at least one vertex from a given set have the Erdős-Pósa property. What about paths that start in a given set A, end in A and have length at least 1000 ? Or subdivided claws with all their endvertices in A?

I will give a brief introduction to the Erdős-Pósa property and discuss some new results along the above mentioned examples.

Date and time: 26/11/2020 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p