Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ https://dr.lib.iasta...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://doi.org/10.31274/etd-2...
Doctoral thesis . 2021 . Peer-reviewed
Data sources: Crossref
versions View all 1 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Two problems in extremal combinatorics

Authors: Neal Riasanovsky, Alex;

Two problems in extremal combinatorics

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 ...

Country
United States
Related Organizations
Keywords

000, extremal combinatorics, Mathematics, graphons, random graphs, 004

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average