Back to search

Georgia Institute of Technology

Counting cliques in graphs with excluded minors

Abstract

dc:description.abstract

This 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 × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/78699

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Shi, Ruilin. Counting cliques in graphs with excluded minors. Doctoral thesis, Georgia Institute of Technology, 2025. https://hdl.handle.net/1853/78699