- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Packing topological minors half-integrally
Open Collections
BIRS Workshop Lecture Videos
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\).
Item Metadata
| Title |
Packing topological minors half-integrally
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-08-23T10:36
|
| 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\).
|
| Extent |
17 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Princeton Universty
|
| Series | |
| Date Available |
2018-04-11
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0365327
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Postdoctoral
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International