#### Degree Type

Dissertation

#### Date of Award

2021

#### Degree Name

Doctor of Philosophy

#### Department

Mathematics

#### Major

Mathematics

#### First Advisor

Ryan Martin

#### Abstract

In this thesis, we focus on two problems in extremal graph theory. Extremal graph theory consists of all problems related to optimizing parameters defined on graphs. The concept of ``editing'' appears in many key results and techniques in extremal graph theory, either as a means to account for error in structural results, or as a quantity to minimize or maximize. A typical problem in spectral extremal graph theory seeks relationships between the extremes of certain graph parameters and the extremes of eigenvalues commonly associated to graphs.

The \emph{edit distance problem} asks the following problem: for any fixed ``forbidden'' graph $F$, how many ``edits'' are needed to ensure that any graph on $n$ vertices can be made to contain no induced copies of $F$. If $F$ is a complete graph, then Tur\'{a}n's Theorem, an early fundamental result in extremal graph theory, provides a precise answer. The \emph{edit distance function} plays an essential role in answering this question and relates to the \emph{speed} of a graph hereditary property $\hh$ as well as the $\hh$-chromatic number of a random graph. The main techniques revolve around so-called \emph{colored regularity graphs (CRGs)}. We find an asymptotically almost sure formula for the edit distance function when $F$ is an Erd\H{o}s-R\'{e}nyi random graph whose density lies in $[1-1/\phi, 1/\phi]\approx [0.382¸0.618]$. As an intermediate step, we make several advances on the application of CRGs, such as the introduction and application of \emph{$p$-prohibited CRGs}.

%In \emph{spectral graph theory}, we ask: given graph $G$ and some matrix $M$ which may be naturally associated to $G$, what do the eigenvalues of $M$ say about $G$? For any $n$-vertex graph $G$, its adjacency matrix $A = A_G$ is the $\{0,1\}$-valued $n\times n$ matrix whose $(u,v)$ entry indicates whether $uv$ is an edge of $G$. In $1999$, Gregory, Hershkowitz, and Kirkland defined the \emph{(adjacency) spread} of a graph as the difference between the maximum and minimum eigenvalues of its adjacency matrix. In their paper, since cited $68$ times, the authors conjectured that the graph on $n$ vertices which maximizes spread is the join of a complete graph on $\lfloor 2n/3\rfloor$ vertices with an independent set on $\lceil n/3\rceil$ vertices. We prove this claim for all $n$ sufficiently large. As an intermediate step, we prove an analogous result for the eigenvalues of \emph{graphons} (equivalently, kernel operators on symmetric functions $W:[0,1]^2\to [0,1]$).

#### DOI

https://doi.org/10.31274/etd-20210609-132

#### Copyright Owner

Alex Neal Riasanovsky

#### Copyright Date

2021-05

#### Language

en

#### File Format

application/pdf

#### File Size

130 pages

#### Recommended Citation

Neal Riasanovsky, Alex, "Two problems in extremal combinatorics" (2021). *Graduate Theses and Dissertations*. 18571.

https://lib.dr.iastate.edu/etd/18571