##
Two problems in extremal combinatorics

##### Date

##### Authors

##### Major Professor

##### Advisor

##### Committee Member

##### Journal Title

##### Journal ISSN

##### Volume Title

##### Publisher

##### Altmetrics

##### Authors

##### Research Projects

##### Organizational Units

##### Journal Issue

##### Is Version Of

##### Versions

##### Series

##### Department

##### 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]$).