Half-integral Erdos-Posa property for topological minors
Fix a family F of graphs, what is the maximum number of disjoint subgraphs of the input graph G where each of them is isomorphic to a member of F? And what is the minimum number of vertices of G required to intersect all such subgraphs? The former is called a packing problem and the latter is called a covering problem. These two optimization problems form a pair of dual integer programming problems. We say F has the Erdos-Posa property if the solutions of these two problems with respect to F can be bounded by functions 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. The main theorem of this talk 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.