Inducibility and Subgraph Density Problems in Graphs

In this thesis, we consider problems in extremal combinatorics concerning the number of copies of a fixed graph in another larger graph. Many of these problems can be phrased in terms of inducibility, i.e. the maximum proportion of induced copies of the smaller graph F in a larger graph G. We also consider how to maximize or minimize the number of copies of F in G when G has a fixed edge-density. We address these problems in a variety of settings, including edge-colored graphs, edge-weighted graphs, oriented graphs, and ordered graphs. In some of these settings, we consider the number of (not necessarily induced) subgraphs of G that are isomorphic to F, while in others we only consider the induced subgraphs of G.

Author dc:creator

• Emily Cairncross (19254259)

• Mathematics

Statement dc:rights

• In Copyright

DOI dc:identifier

https://doi.org/10.25417/uic.32994233.v1

OAI identifier oai:identifier

oai:figshare.com:article/32994233