Some Extremal Problems for Hereditary Properties of Graphs

Abstract

Given an infinite hereditary property of graphs $\mathcal{P}$, the principal extremal parameter of $\mathcal{P}$ is the value
\[ \pi\left( \mathcal{P}\right) =\lim_{n\rightarrow\infty}\binom{n}{2}^{-1}\max\{e\left( G\right) :\text{ }G\in\mathcal{P}\text{ and }v\left(
G\right) =n\}.
\]
The Erdős-Stone theorem gives $\pi\left( \mathcal{P}\right) $ if $\mathcal{P}$ is monotone, but this result does not apply to hereditary $\mathcal{P}$. Thus, one of the results of this note is to establish $\pi\left( \mathcal{P}\right) $ for any hereditary property $\mathcal{P}.$

Similar questions are studied for the parameter $\lambda^{\left( p\right)}\left( G\right)$, defined for every real number $p\geq1$ and every graph $G$ of order $n$ as
\[
\lambda^{\left( p\right) }\left( G\right) =\max_{\left\vert x_{1}\right\vert^{p}\text{ }+\text{ }\cdots\text{ }+\text{ }\left\vert x_{n}\right\vert ^{p} \text{ }=\text{ }1}2\sum_{\{u,v\}\in E\left( G\right) }x_{u}x_{v}.
\]
It is shown that the limit
\[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) =\lim_{n\rightarrow
\infty}n^{2/p-2}\max\{\lambda^{\left( p\right) }\left( G\right) :\text{ }G\in \mathcal{P}\text{ and }v\left( G\right) =n\}
\]
exists for every hereditary property $\mathcal{P}$.

A key result of the note is the equality \[
\lambda^{(p)}\left( \mathcal{P}\right) =\pi\left( \mathcal{P}\right) ,
\]
which holds for all $p>1.$ In particular, edge extremal problems and
spectral extremal problems for graphs are asymptotically equivalent.