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

#### Keywords

extremal problems; Turán problems; hereditary property; largest eigenvalue

Full Text: PDF