Some extremal problems for hereditary properties of graphs (Q405091): Difference between revisions

Summary: 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\to\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| x_{1}\right|^{p}\text{ }+\text{ }\cdots\text{ }+\text{ }\left| x_{n}\right| ^{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\to \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.