Some extremal problems for hereditary properties of graphs (Q405091): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C75 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C50 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C65 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6340115 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
extremal problems | |||
Property / zbMATH Keywords: extremal problems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Turán problems | |||
Property / zbMATH Keywords: Turán problems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
hereditary property | |||
Property / zbMATH Keywords: hereditary property / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
largest eigenvalue | |||
Property / zbMATH Keywords: largest eigenvalue / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1305.1072 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4398864 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Structure of Edge Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5578805 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5544083 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the structure of linear graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5567712 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Spectral Extremal Problems for Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5512796 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Maxima for Graphs and a New Proof of a Theorem of Turán / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graphs with many <i>r</i> -cliques have large complete <i>r</i> -partite subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some new results in extremal graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Analytic methods for uniform hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5548826 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4200109 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5781249 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:47, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some extremal problems for hereditary properties of graphs |
scientific article |
Statements
Some extremal problems for hereditary properties of graphs (English)
0 references
4 September 2014
0 references
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.
0 references
extremal problems
0 references
Turán problems
0 references
hereditary property
0 references
largest eigenvalue
0 references