# Open Collections

## BIRS Workshop Lecture Videos

### Packing topological minors half-integrally Liu, Chun-Hung

#### Description

The packing problem and the covering problem are two general optimization problems that form a pair of dual integer programming problems. Fix a family \(F\) of graphs, the packing problem asks for the maximum number of disjoint subgraphs of the input graph \(G\) where each is isomorphic to a member of \(F\), and the covering problem asks for the minimum number of vertices of \(G\) required to intersect all such subgraphs. We say \(F\) has the Erdos-Posa property if the solutions of these two problems with respect to \(F\) can be bounded in terms of each other. It is well-known that if \(H\) is a graph such that the set of \(H\) minors has the Erdos-Posa property, then \(H\) must be planar. Thomas conjectured that the planarity is not required if half-integral solutions of the packing problem are allowed. In other words, he conjectured that for every graph \(H\), there exists a function \(f\) such that for every graph \(G\), either \(G\) contains \(k\) subgraphs where each of them is an \(H\) minor such that every vertex of \(G\) is contained in at most two of those subgraphs, or there exists a set of at most \(f(k)\) vertices intersecting all \(H\) minors in \(G\). In this talk, we prove that the same statement holds for topological minors. It is a stronger statement that easily implies Thomas' conjecture. Namely, we prove that for every graph \(H\), there exists a function \(f\) such that for every graph \(G\), either \(G\) contains \(k\) subdivisions of \(H\) such that every vertex of \(G\) is contained in at most two of them, or there exists a set of at most \(f(k)\) vertices intersecting all subdivisions of \(H\) in \(G\).