Final doctoral examination and defense of dissertation of Yan Wang

Monday, April 10, 2017 - 3:00pm
Skiles 006
Title: Subdivisions of complete graphs
Advisor: Professor Xingxing Yu, School of Mathematics
Committee: Professor Robin Thomas, School of Mathematics
  Professor Prasad Tetali, School of Mathematics
  Professor Lutz Warnke, School of Mathematics
  Professor Richard Peng, College of Computing
Reader: Prof. Ken-ichi Kawarabayashi, National Institute of Informatics and JST ERATO Kawarabayashi Project

Summary: A subdivision of a graph G, also known as a topological G and denoted by TG, is a graph obtained from G by replacing certain edges of G with internally vertex-disjoint paths. This dissertation has two parts. The first part studies a structural problem and the second part studies an extremal problem.


In the first part of this dissertation, we focus on TK_5, or subdivisions
of K_5. A well-known theorem of Kuratowski in 1932 states that a graph is
planar if, and only if, it does not contain a subdivision of K_5 or
K_{3,3}. Wagner proved in 1937 that if a graph other than K_5 does not
contain any subdivision of K_{3,3} then it is planar or it admits a cut of
size at most 2. Kelmans and, independently, Seymour conjectured in the
1970s that if a graph does not contain any subdivision of K_5 then it is
planar or it admits a cut of size at most 4. In this dissertation, we give
a proof of the Kelmans-Seymour conjecture. We also discuss several related
results and problems.

The second part of this dissertation concerns subdivisions of large cliques
in C_4-free graphs. Mader conjectured that every C_4-free graph with
average degree d contains TK_l with l = \Omega(d). Komlos and Szemeredi
reduced the problem to expanders and proved Mader's conjecture for n-vertex
expanders with average degree d < exp( (log n)^(1/8) ). In this
dissertation, we show that Mader's conjecture is true for n-vertex
expanders with average degree d < n^0.3, which improves Komlos and
Szemeredi's quasi-polynomial bound to a polynomial bound. As a consequence,
we show that every C_4-free graph with average degree d contains a TK_l
with l = \Omega(d/(log d)^c) for any c > 3/2. We note that Mader's
conjecture has been recently verified by Liu and Montgomery.