Some extremal problems for hereditary properties of graphs

Vladimir Nikiforov¹

¹University of Memphis

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

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 andspectral extremal problems for graphs are asymptotically equivalent.

Détail

DOI : 10.37236/3419

Classification : 05C35, 05C75, 05C50, 05C65
Mots-clés : extremal problems, Turán problems, hereditary property, largest eigenvalue