Some extremal problems for hereditary properties of graphs
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.
- Analytic methods for uniform hypergraphs
- Graphs with many r -cliques have large complete r -partite subgraphs
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 1179517 (Why is no real title available?)
- scientific article; zbMATH DE number 3224335 (Why is no real title available?)
- scientific article; zbMATH DE number 3258858 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3285073 (Why is no real title available?)
- scientific article; zbMATH DE number 3298603 (Why is no real title available?)
- scientific article; zbMATH DE number 3041944 (Why is no real title available?)
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On the Structure of Edge Graphs
- On the structure of linear graphs
- Some new results in extremal graph theory
- Spectral extremal problems for hypergraphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Degenerate Turán problems for hereditary properties
- Strong forms of stability from flag algebra calculations
- The extremal \(p\)-spectral radius of Berge hypergraphs
- Analytic methods for uniform hypergraphs
- The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs
- The f-factor problem for graphs and the hereditary property
- A jump to the Bell number for hereditary graph properties
- Hereditarily infinite-dimensional property for asymptotic dimension and graphs with large girth
- Extremal problems for the p-spectral radius of graphs
- Maximal graphs with respect to hereditary properties
- scientific article; zbMATH DE number 1416461 (Why is no real title available?)
- The α-normal labelling method for computing the p-spectral radii of uniform hypergraphs
- Extremal sets of graphs in the problem of demarcation in the family of hereditary closed classes of graphs
- On the jump number problem in hereditary classes of bipartite graphs
- On spectral theory of a k-uniform directed hypergraph
- Spectral Turán-type problems on cancellative hypergraphs
- Spectral Turán problems on the expansion of matchings
This page was built for publication: Some extremal problems for hereditary properties of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405091)
