Abstract
dc:description.abstractThis thesis explores Turán-type extremal problems in graphs that exclude certain minors, focusing on the maximum number of k-cliques such graphs can contain. The first part of the thesis studies planar graphs, which forbid K5 and K3,3 as minors. We determine the maximum number of edges is in a planar graph that contains no cycle of length k, and establish a general upper bound for the number of edges in a planar graph avoiding Ck for any k≥11. The second part addresses the maximum number of k-cliques in Kt-minor-free graphs. We show essentially sharp bounds on the maximum possible number of cliques of order k in a Kt-minor-free graph on n vertices. More precisely, we determine a function C(k,t) such that for each k<t with t−k>>log2 t, every Kt-minor-free graph on n vertices has at most n⋅C(k,t)1+o(1) cliques of order k. We also show that this bound is sharp by constructing a Kt-minor-free graph on n vertices with C(k,t)n cliques of order k. This result answers a question of Wood and Fox–Wei asymptotically up to an ot(1) factor in the exponent, except in the extreme case where k is very close to t.
Degree
thesis:*- Level thesis:degree_level
- Doctoral
- Department dc:contributor.department
- Mathematics
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shi, Ruilin
- Advisors dc:contributor.advisor
-
- Wei, Fan
- Yu, Xingxing
- Committee members dc:contributor.committeemember
-
- Blekherman, Grigoriy
- He, Xiaoyu
- McCarty, Rose
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/78699