%% This document created by Scientific Word (R) Version 3.5 % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages % we recommend the graphicx package for importing figures % use this command to create hyperlinks (optional and recommended) % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \documentclass[12pt]{article} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \setcounter{MaxMatrixCols}{10} %TCIDATA{OutputFilter=Latex.dll} %TCIDATA{Version=5.00.0.2552} %TCIDATA{} %TCIDATA{LastRevised=Saturday, January 11, 2014 17:02:49} %TCIDATA{} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} %\input{tcilatex} \begin{document} \title{\textbf{Some extremal problems for hereditary properties of graphs}} \author{Vladimir Nikiforov \\ %EndAName {\small Department of Mathematical Sciences }\\ [-0.8ex] {\small University of Memphis, Memphis, TN, USA }\\ {\small \texttt{vnikifrv@memphis.edu}}\\ } \date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\ {\small Mathematics Subject Classifications: 05C65, 05C35}} \maketitle \begin{abstract} Given an infinite hereditary property of graphs $\mathcal{P},$ the principal extremal parameter of $\mathcal{P}$ is the value% \begin{equation*} \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\}. \end{equation*} The Erd\H{o}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 \begin{equation*} \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}. \end{equation*} It is shown that the limit% \begin{equation*} \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\} \end{equation*} exists for every hereditary property $\mathcal{P}$. A key result of the note is the equality% \begin{equation*} \lambda^{(p)}\left( \mathcal{P}\right) =\pi\left( \mathcal{P}\right) , \end{equation*} which holds for all $p>1.$ In particular, edge extremal problems and spectral extremal problems for graphs are asymptotically equivalent. \bigskip\noindent \textbf{Keywords:} extremal problems; Tur\'{a}n problems; hereditary property; largest eigenvalue. \end{abstract} \section{Introduction and main results} In this note we study problems stemming from the following one:\ \begin{problem} \label{p1}What is the maximum number of edges in a graph $G$ of order $n$ if $G$ belongs to some hereditary property $P$. \end{problem} Let us recall the basics of graph properties: A \textbf{graph property} is just a family of graphs closed under isomorphisms. A property is called \textbf{monotone }if it is closed under taking subgraphs, and \textbf{% hereditary }if it is closed under taking induced subgraphs. Given a set of graphs $\mathcal{F},$ the family of all graphs that do not contain any $F\in \mathcal{F}$ as a subgraph is a monotone property, denoted by $Mon\left( \mathcal{F}\right) .$ Likewise, the family of all graphs that do not contain any $F\in \mathcal{F}$ as an induced subgraph is a hereditary property, denoted as $Her\left( \mathcal{F}\right) .$ It seems that the classically shaped Problem \ref{p1} has been disregarded in the rich literature on hereditary properties, so in this paper we shall fill in this gap. Note, however, that for monotone properties the theorem of Erd\H{o}s and Stone provides a well-known solution, outlined in Proposition % \ref{proES} below. Writing $\mathcal{P}_{n}$ for the set of all graphs of order $n$ in a property $\mathcal{P},$ now Problem \ref{p1} reads as: \medskip \emph{Given a hereditary property }$\mathcal{P}$\emph{, find} \begin{equation} ex\left( \mathcal{P},n\right) =\max_{G\in\mathcal{P}_{n}}e\left( G\right) . \label{maxed} \end{equation} Finding $ex\left( \mathcal{P},n\right) $ exactly seems hopeless for arbitrary $\mathcal{P}$. A more feasible approach has been suggested by Katona, Nemetz and Simonovits in \cite{KNS64} who proved the following fact: \begin{proposition} \label{proKNS}If $\mathcal{P}$ is a hereditary property, then the limit \begin{equation*} \pi\left( \mathcal{P}\right) =\lim_{n\rightarrow\infty}ex\left( \mathcal{P}% ,n\right) \binom{n}{2}^{-1} \end{equation*} exists. \end{proposition} In particular, for monotone properties Erd\H{o}s and Simonovits \cite{ErSi66} observed the following consequence of the Erd\H{o}s-Stone theorem \cite% {ErSt46}: \begin{proposition} \label{proES}If a monotone property $\mathcal{P}$ is given as $\mathcal{P}% =Mon\left( \mathcal{F}\right) $ for some nonempty family $\mathcal{F},$ then \begin{equation*} \pi\left( Mon\left( \mathcal{F}\right) \right) =1-1/\chi, \end{equation*} where $\chi=\min\left\{ \chi\left( F\right) :F\in\mathcal{F}\right\} .$ \end{proposition} Unfortunately, $\pi\left( \mathcal{P}\right) $ cannot be determined in the same simple way for a general hereditary property $\mathcal{P}$, and so one of the aims of this note is to establish $\pi\left( \mathcal{P}\right) $ for such $\mathcal{P}$. However, our main focus is on extremal problems about a more general graph parameter, denoted by $\lambda^{\left( p\right) }\left( G\right) $ and defined as follows: \medskip \emph{Given a graph }$G$\emph{\ and a real number }$p\geq1,$\emph{\ let} \begin{equation*} \lambda^{\left( p\right) }\left( G\right) =\max_{\left\vert x_{1}\right\vert ^{p}+\text{ }\cdots\text{ }+\left\vert x_{n}\right\vert ^{p}=1}2\sum_{\left\{ u,v\right\} \in E\left( G\right) }x_{u}x_{v}. \end{equation*} Note that $\lambda^{\left( 2\right) }\left( G\right) $ is the well-studied spectral radius of $G,$ and also that $\lambda^{\left( 1\right) }\left( G\right) $ is a another much studied graph parameter, known as the Lagrangian% \footnote{% Let us note that this use of the name \emph{Lagrangian} is at odds with the tradition. Indeed, names as \emph{Laplacian, Hessian, Gramian, Grassmanian}, etc., usually denote a structured object like matrix, operator, or manifold, and not just a single number.} of $G$. Moreover, letting $% p\rightarrow\infty, $ one can show that $\lambda^{\left( p\right) }\left( G\right) \rightarrow e\left( G\right) .$ So $\lambda^{\left( p\right) }\left( G\right) $ is a common generalization of three central parameters in extremal graph theory. The parameter $\lambda^{\left( p\right) }\left( G\right) $ has been introduced and studied for uniform hypergraphs first by Keevash, Lenz and Mubayi in \cite{KLM13}, and next by the author in \cite{NikB} and \cite{NikC}% . Here we shall study $\lambda^{\left( p\right) }\left( G\right) $ in the same role as $e\left( G\right) $ in equation (\ref{maxed}), obtaining thus the following problem. \begin{problem} \label{p2}Given a hereditary property $\mathcal{P},$ find% \begin{equation} \lambda^{\left( p\right) }\left( \mathcal{P},n\right) =\max_{G\in \mathcal{P}% _{n}}\lambda^{\left( p\right) }\left( G\right) . \label{maxlam} \end{equation} \end{problem} As for $ex\left( \mathcal{P},n\right) ,$ finding $\lambda^{\left( p\right) }\left( \mathcal{P},n\right) $ seems hopeless for arbitrary $\mathcal{P},$ so we begin with an analog to Proposition \ref{proKNS}. \begin{theorem} \label{thlim}Let $p\geq1.$ If $\mathcal{P}$ is a hereditary property, then the limit \begin{equation*} \lambda^{\left( p\right) }\left( \mathcal{P}\right) =\lim_{n\rightarrow \infty}\lambda^{\left( p\right) }\left( \mathcal{P},n\right) n^{\left( 2/p\right) -2} \end{equation*} exists. \end{theorem} The main goal of this note is to find $\lambda^{\left( p\right) }\left( \mathcal{P}\right) $ for every $\mathcal{P}$ and every $p\geq1.$ It turns out that $\lambda^{\left( p\right) }\left( \mathcal{P}\right) $ and $% \pi\left( \mathcal{P}\right) $ are almost identical. Indeed, general results proved in \cite{NikB} imply that $\lambda^{\left( p\right) }\left( \mathcal{P% }\right) =\pi\left( \mathcal{P}\right) $ for every $p>1,$ and also $% \lambda^{\left( 1\right) }\left( \mathcal{P}\right) \geq\pi\left( \mathcal{P}% \right) .$ In this note we give an alternative direct proof of these results, and we find $\pi\left( \mathcal{P}\right) $ explicitly.\medskip Before going further we need some definitions. Recall that a \textbf{% complete }$r$\textbf{-partite graph} is a graph whose vertices can be split into $r$ nonempty independent sets so that all edges between vertices of different classes are present. In particular, an $1$-partite graph is just a set of isolated vertices. Further, note that every hereditary property $\mathcal{P}$ can be represented as $\mathcal{P}=Her\left( \mathcal{F}\right) $ for some family $% \mathcal{F},$ so hereafter we shall assume that every hereditary property is given as $\mathcal{P}=Her\left( \mathcal{F}\right) $ for some explicit family $\mathcal{F}.$ Next, for every family of graphs $\mathcal{F},$ define the parameters $% \underline{\omega}\left( \mathcal{F}\right) $ and $\beta\left( \mathcal{F}% \right) $ as \begin{align*} \underline{\omega}\left( \mathcal{F}\right) & =\left\{ \begin{array}{l} 0,\text{ if }\mathcal{F}\text{ contains no cliques;} \\ \min\left\{ r:K_{r}\in\mathcal{F}\right\} ,\text{ otherwise.}% \end{array} \right. \\ \beta\left( \mathcal{F}\right) & =\left\{ \begin{array}{l} 0,\text{ if }\mathcal{F}\text{ contains no complete partite graphs;} \\ \min\left\{ r:\mathcal{F}\text{ contains a complete }r\text{-partite graph}% \right\} ,\text{ otherwise.}% \end{array} \right. \end{align*} The parameters $\underline{\omega}\left( \mathcal{F}\right) $ and $% \beta\left( \mathcal{F}\right) $ are quite informative about the hereditary property $Her\left( \mathcal{F}\right) $ as seen in the following observation. \begin{proposition} \label{proinf}If the property $\mathcal{P}$ $=Her\left( \mathcal{F}\right) $ is infinite, then $\underline{\omega}\left( \mathcal{F}\right) =0$ or $% \underline{\omega}\left( \mathcal{F}\right) \geq2$ and $\beta\left( \mathcal{% F}\right) \geq2.$ \end{proposition} \begin{proof} Suppose that $\underline{\omega}\left( \mathcal{F}\right) \neq0.$ If $\underline{\omega}\left( \mathcal{F}\right) =1,$ then $\mathcal{P}$ is empty, so we shall suppose that $\underline{\omega}\left( \mathcal{F}\right) \geq2.$ This implies that $\beta\left( \mathcal{F}\right) >0,$ as $\mathcal{F}$ contains $K_{r}$ for some $r\geq2$ and $K_{r}$ is a complete $r$-partite graph. If $\beta\left( \mathcal{F}\right) =1,$ then $\mathcal{F}$ contains a graph $F$ consisting of isolated vertices, let say $s$ be the order of $F.$ Choose a member $G\in\mathcal{P}$ with $v\left( G\right) \geq r\left( K_{r},K_{s}\right) ,$ where $r\left( K_{r}% ,K_{s}\right) $ is the Ramsey number of $K_{r}$ vs. $K_{s}.$ Thus, $G$ contains either a $K_{r}$ or an independent set on $s$ vertices, both of which are forbidden. This contradiction shows that $\beta\left( \mathcal{F}\right) \geq2,$ proving Proposition \ref{proinf}. \end{proof} Clearly the study of (\ref{maxed}) and (\ref{maxlam}) makes sense only if $% \mathcal{P}$ is infinite, and Proposition \ref{proinf} provides a necessary condition for this feature of $\mathcal{P}$. Now, the following theorem completely determines $\pi\left( \mathcal{P}\right) .$ \begin{theorem} \label{thpi}Let $\mathcal{F}$ be a family of graphs. If the property $% \mathcal{P}=Her\left( \mathcal{F}\right) $ is infinite, then \begin{equation*} \pi\left( \mathcal{P}\right) =\left\{ \begin{array}{l} 1,\text{ \ \ \ \ \ \ \ \ \ \ \ \ if }\underline{\omega}\left( \mathcal{F}% \right) =0; \\ 1-\frac{1}{\beta\left( \mathcal{F}\right) -1},\text{ otherwise.}% \end{array} \right. . \end{equation*} \end{theorem} Let us turn now to the study of $\lambda^{\left( p\right) }\left( \mathcal{P}% \right) .$ As mentioned above, in \cite{NikB} it has been proved that $% \pi\left( \mathcal{P}\right) =\lambda^{\left( p\right) }\left( \mathcal{P}% \right) $ for $p>1;$ however, for reader's sake we shall establish this identity directly. \begin{theorem} \label{thlam} Let $p>1$ and let $\mathcal{F}$ be a family of graphs. If the property $\mathcal{P}=Her\left( \mathcal{F}\right) $ is infinite, then \begin{equation*} \lambda^{\left( p\right) }\left( \mathcal{P}\right) =\left\{ \begin{array}{l} 1,\text{ \ \ \ \ \ \ \ \ \ \ \ \ if }\underline{\omega}\left( \mathcal{F}% \right) =0; \\ 1-\frac{1}{\beta\left( \mathcal{F}\right) -1},\text{ otherwise.}% \end{array} \right. . \end{equation*} \end{theorem} To complete the description of $\lambda^{\left( p\right) }\left( \mathcal{P}% \right) $ we need to determine the dependence of $\lambda^{\left( 1\right) }\left( \mathcal{P}\right) $ on $\mathcal{P}$. Using the well-known idea of Motzkin and Straus \cite{MoSt65}, we come up with the following theorem, whose easy proof we omit. \begin{theorem} \label{thlam1}If $\mathcal{P}$ is an infinite hereditary property, then $% \lambda^{\left( 1\right) }\left( \mathcal{P}\right) =1-1/r$ if $r$ is the size of the largest clique in $\mathcal{P},$ and $\lambda^{\left( 1\right) }\left( \mathcal{P}\right) =1$ if $\mathcal{P}$ contains arbitrary large cliques. \end{theorem} \bigskip The next section contains proofs of Theorems \ref{thlim}, \ref{thpi} and \ref% {thlam}, and some auxiliary statements. In the final section we outline a line of possible future research. \section{\label{Pf}Proofs} \subsection{Some preliminary results} Below we state several results necessary for the proof of our key Theorem % \ref{thlam}. The first one follows from a result in \cite{NikB}, but for reader's sake we give its short proof here. \begin{theorem} \label{maxlK}Let $p\geq1.$ If $G$ is a graph with $m$ edges and $n$ vertices, with no $K_{r+1},$ then% \begin{equation} \lambda^{\left( p\right) }\left( G\right) \leq\left( 1-\frac{1}{r}\right) ^{1/p}\left( 2m\right) ^{1-1/p} \label{in1} \end{equation} and \begin{equation} \lambda^{\left( p\right) }\left( G\right) \leq\left( 1-\frac{1}{r}\right) n^{2-2/p}. \label{in2} \end{equation} \end{theorem} \begin{proof} Indeed, let $\mathbf{x}=\left( x_{1},\ldots,x_{n}\right) $ be a vector such that $\left\vert x_{1}\right\vert ^{p}+\cdots+\left\vert x_{n}\right\vert ^{p}=1$ and \[ \lambda^{\left( p\right) }\left( G\right) =2\sum_{\left\{ u,v\right\} \in E\left( G\right) }x_{u}x_{v}. \] Applying the Power Mean Inequality, we see that \begin{align*} \lambda^{\left( p\right) }\left( G\right) & =2\sum_{\left\{ u,v\right\} \in E\left( G\right) }x_{u}x_{v}\leq2\sum_{\left\{ u,v\right\} \in E\left( G\right) }\left\vert x_{u}\right\vert \left\vert x_{v}\right\vert \\ & \leq\left( 2m\right) ^{1-1/p}\left( 2\sum_{\left\{ u,v\right\} \in E\left( G\right) }\left\vert x_{u}\right\vert ^{p}\left\vert x_{v}% \right\vert ^{p}\right) ^{1/p}. \end{align*} Now, the result of Motzkin and Straus \cite{MoSt65} impies that \[ 2\sum_{\left\{ u,v\right\} \in E\left( G\right) }\left\vert x_{u}% \right\vert ^{p}\left\vert x_{v}\right\vert ^{p}\leq1-\frac{1}{r}, \] and inequality (\ref{in1}) follows. Finally, inequality (\ref{in2}) follows from (\ref{in1}) by Tur\'{a}n's inequality $2m\leq\left( 1-1/r\right) n^{2}.$ \end{proof} Note, in particular, that $\lambda^{\left( p\right) }\left( G\right) \leq\left( 2m\right) ^{1-1/p}.$ This simple bound will be used in the proof of the following proposition. \begin{proposition} \label{pro10}Let $p\geq1,$ $k>1$ and $G_{1}$ and $G_{2}$ be graphs on the same vertex set. If $G_{1}$ and $G_{2}$ differ in at most $k$ edges, then% \begin{equation*} \left\vert \lambda^{\left( p\right) }\left( G_{1}\right) -\lambda^{\left( p\right) }\left( G_{2}\right) \right\vert \leq\left( 2k\right) ^{1-1/p}. \end{equation*} \end{proposition} \begin{proof} Let $V=V\left( G_{1}\right) =V\left( G_{2}\right) $ and write $G_{12}$ for the graph with $V\left( G_{12}\right) =V$ and $E\left( G_{12}\right) =E\left( G_{1}\right) \cap E\left( G_{2}\right) .$ We may and shall assume that $\lambda^{\left( p\right) }\left( G_{1}\right) \geq\lambda^{\left( p\right) }\left( G_{2}\right) .$ Write $G_{3}$ for the graph with $V\left( G_{3}\right) =V$ and $E\left( G_{3}\right) =E\left( G_{1}\right) \backslash E\left( G_{2}\right) .$ In view of $G_{12}\subset G_{2},$ we have% \begin{align*} 0 & \leq\lambda^{\left( p\right) }\left( G_{1}\right) -\lambda^{\left( p\right) }\left( G_{2}\right) =\lambda^{\left( p\right) }\left( G_{1}\right) -\lambda^{\left( p\right) }\left( G_{12}\right) -\left( \lambda^{\left( p\right) }\left( G_{2}\right) -\lambda^{\left( p\right) }\left( G_{12}\right) \right) \\ & \leq\lambda^{\left( p\right) }\left( G_{1}\right) -\lambda^{\left( p\right) }\left( G_{12}\right) \leq\lambda^{\left( p\right) }\left( G_{3}\right) \leq\left( 2e\left( G_{3}\right) \right) ^{1-1/p}\\ & \leq\left( 2k\right) ^{1-1/p}, \end{align*} proving Proposition \ref{pro10}. \end{proof} Further, let us recall the following particular version of the Removal Lemma, which is a consequence of the Szemer\'{e}di Regularity Lemma (\cite% {Sze76}, \cite{Bol98}):\medskip \textbf{Removal Lemma} \emph{For all }$r\geq3$\emph{\ and }$\varepsilon >0,$% \emph{\ there exists }$\delta=\delta\left( r,\varepsilon\right) >0$\emph{\ such that if }$G$\emph{\ is a graph of order }$n,$\emph{\ with }$k_{r}\left( G\right) <\delta n^{r},$\emph{\ then there is a graph }$G_{0}\subset G$\emph{% \ such that }$e\left( G_{0}\right) \geq e\left( G\right) -\varepsilon n^{2}$% \emph{\ and }$k_{r}\left( G_{0}\right) =0.\medskip$ Finally, we shall need the following theorem proved in \cite{Nik08}:\medskip \textbf{Theorem A }\emph{For all }$r\geq2$\emph{\ and }$\varepsilon>0,$\emph{% \ there exists }$\delta=\delta\left( r,\varepsilon\right) >0$\emph{\ such that if }$G$\emph{\ a graph of order }$n$\emph{\ with }$k_{r}\left( G\right) >\varepsilon n^{r},$\emph{\ then }$G$\emph{\ contains a }$K_{r}\left( s\right) $\emph{\ with }$s=\left\lfloor \delta\log n\right\rfloor .$ \subsection{Proof of Theorem \protect\ref{thlim}} \begin{proof} Set for short $\lambda_{n}^{\left( p\right) }=\lambda^{\left( p\right) }\left( \mathcal{P},n\right) .$ Let $G\in\mathcal{P}_{n}$ be such that $\lambda_{n}^{\left( p\right) }=\lambda^{\left( p\right) }\left( G\right) $ and let $\mathbf{x}=\left( x_{1},\ldots,x_{n}\right) $ be a vector with $\left\vert x_{1}\right\vert ^{p}+\cdots+\left\vert x_{n}% \right\vert ^{p}=1$ and \[ \lambda_{n}^{\left( p\right) }=\lambda^{\left( p\right) }\left( G\right) =2\sum_{\left\{ u,v\right\} \in E\left( G\right) }x_{u}x_{v}. \] If $p=1,$ we obviously have $\lambda_{n}^{\left( 1\right) }\geq\lambda _{n-1}^{\left( 1\right) }$ and in view of \[ \lambda_{n}^{\left( 1\right) }=2\sum_{\left\{ u,v\right\} \in E\left( G\right) }x_{u}x_{v}\leq2\sum_{1\leq i1.$ Since $\left\vert x_{1}\right\vert ^{p}+\cdots +\left\vert x_{n}\right\vert ^{p}=1,$ there is a vertex $k\in V\left( G\right) $ such that $\left\vert x_{k}\right\vert ^{p}\leq1/n.$ Write $G-k$ for the graph obtained from $G$ by omitting the vertex $k,$ and let $\mathbf{x}^{\prime}=\left( x_{1}^{\prime},\ldots,x_{n-1}^{\prime}\right) $ be the $\left( n-1\right) $-vector obtained from $\mathbf{x}$ by omitting the entry $x_{k}.$ The eigenequation for $\lambda^{\left( p\right) }\left( G\right) $ and the vertex $k$ is% \[ \lambda^{\left( p\right) }\left( G\right) x_{k}\left\vert x_{k}\right\vert ^{p-2}=\sum_{\left\{ k,i\right\} \in E\left( G\right) }x_{i}. \] Hence, we see that% \begin{align*} 2\sum_{\left\{ u,v\right\} \in E\left( G-k\right) }x_{u}^{\prime}% x_{v}^{\prime} & =2\sum_{\left\{ u,v\right\} \in E\left( G\right) }% x_{u}x_{v}-2x_{k}\sum_{\left\{ k,i\right\} \in E\left( G\right) }x_{i}\\ & =\lambda^{\left( p\right) }\left( G\right) -2x_{k}\left( \lambda^{\left( p\right) }\left( G\right) x_{k}\left\vert x_{k}\right\vert ^{p-2}\right) =\lambda_{n}^{\left( p\right) }\left( 1-2\left\vert x_{k}\right\vert ^{p}\right) . \end{align*} Since $\mathcal{P}$ is a hereditary property, $G-k\in\mathcal{P}_{n-1},$ and therefore,% \[ 2\sum_{\left\{ u,v\right\} \in E\left( G-k\right) }x_{u}^{\prime}% x_{v}^{\prime}\leq\lambda^{\left( p\right) }\left( G-k\right) \left\vert \mathbf{x}^{\prime}\right\vert _{p}^{2}=\lambda^{\left( p\right) }\left( G-k\right) \left( 1-\left\vert x_{k}\right\vert ^{p}\right) ^{2/p}% \leq\lambda_{n-1}^{\left( p\right) }\left( 1-\left\vert x_{k}\right\vert ^{p}\right) ^{2/p}. \] Thus, we obtain% \begin{equation} \lambda_{n}^{\left( p\right) }\leq\lambda_{n-1}^{\left( p\right) }% \frac{\left( 1-\left\vert x_{k}\right\vert ^{p}\right) ^{2/p}}{\left( 1-2\left\vert x_{k}\right\vert ^{p}\right) }. \label{in3}% \end{equation} Note that the function \[ f\left( y\right) =\frac{\left( 1-y\right) ^{2/p}}{1-2y}% \] is nondecreasing in $y$ for $0\leq y\leq1/n$ and $n$ sufficiently large. Indeed,% \begin{align*} \frac{df\left( y\right) }{dy} & =\frac{-\frac{2}{p}\left( 1-y\right) ^{2/p-1}\left( 1-2y\right) +2\left( 1-y\right) ^{2/p}}{\left( 1-2y\right) ^{2}}\\ & =\left( -\frac{1}{p}\left( 1-2y\right) +\left( 1-y\right) \right) \frac{2\left( 1-y\right) ^{2/p-1}}{\left( 1-2y\right) ^{2}}\\ & =\left( -\left( \frac{1}{p}-1\right) +\left( \frac{2}{p}-1\right) y\right) \frac{2\left( 1-y\right) ^{2/p-1}}{\left( 1-2y\right) ^{2}}\geq0 \end{align*} Here we use the fact that $1/p-1>0$ and that $\left( 2/p-1\right) y$ tends to $0$ when $n$ $\rightarrow\infty.$ Hence, in view of (\ref{in3}), we find that for $n$ large enough \[ \lambda_{n}^{\left( p\right) }\leq\lambda_{n-1}^{\left( p\right) }f\left( \left\vert x_{k}\right\vert ^{p}\right) \leq\lambda_{n-1}^{\left( p\right) }f\left( \frac{1}{n}\right) =\lambda_{n-1}^{\left( p\right) }% \frac{n\left( 1-1/n\right) ^{2/p}}{\left( n-2\right) }, \] and so \[ \frac{\lambda_{n}^{\left( p\right) }n^{2/p}}{n\left( n-1\right) }\leq \frac{\lambda_{n-1}^{\left( p\right) }\left( n-1\right) ^{2/p}}{\left( n-1\right) \left( n-2\right) }. \] Therefore, the sequence% \[ \left\{ \frac{\lambda_{n}^{\left( p\right) }n^{2/p}}{n\left( n-1\right) }\right\} _{n=1}^{\infty}% \] is nonincreasing, and so it is converging, completing the proof of Theorem \ref{thlim}. \end{proof} \subsection{Proof of Theorem \protect\ref{thpi}} \begin{proof} Since $\mathcal{P}$ is infinite, Proposition \ref{proinf} implies that $\underline{\omega}\left( \mathcal{F}\right) =0$ or $\underline{\omega }\left( \mathcal{F}\right) \geq2$ and $\beta\left( \mathcal{F}\right) \geq2.$ If $\underline{\omega}\left( \mathcal{F}\right) =0,$ then $K_{n}% \in\mathcal{P}_{n},$ because all induced subgraphs of $K_{n}$ are complete and therefore do not belong to $\mathcal{F}$. Hence, \[ ex\left( \mathcal{P},n\right) =\binom{n}{2}; \] and so, $\pi\left( \mathcal{P}\right) =1.$ Now assume that $r=\underline{\omega}\left( \mathcal{F}\right) \geq2$ and $\beta=\beta\left( \mathcal{F}\right) \geq2.$ We shall prove that $T_{\beta-1}\left( n\right) \in\mathcal{P}_{n},$ where $T_{\beta-1}\left( n\right) $ is the complete $\left( \beta-1\right) $-partite Tur\'{a}n graph of order $n.$ Indeed all induced subgraphs of $T_{\beta-1}\left( n\right) $ are complete $r$-partite graphs for some $r\leq\beta-1$, so should one of them belong to $\mathcal{F},$ we would have $\beta\left( \mathcal{F}\right) \leq\beta-1=\beta\left( \mathcal{F}\right) -1,$ which is a contradiction. Therefore, \[ ex\left( \mathcal{P},n\right) \geq e\left( T_{\beta-1}\left( n\right) \right) =\left( 1-\frac{1}{\beta-1}+o\left( 1\right) \right) \binom{n}% {2}, \] and so% \[ \pi\left( \mathcal{P}\right) \geq1-\frac{1}{\beta\left( \mathcal{F}\right) -1}. \] To finish the proof we shall prove the opposite inequality. Let $F\in \mathcal{F}$ be a complete $\beta$-partite graph, which exists by the definition of $\beta\left( \mathcal{F}\right) ;$ let $s$ be the maximum of the sizes of its vertex classes. Let $\varepsilon>0$ and set $t=r\left( K_{r},K_{s}\right) ,$ where $r\left( K_{r},K_{s}\right) $ is the Ramsey number of $K_{r}$ vs. $K_{s}.$ If $n$ is large enough and $G\in\mathcal{P}% _{n}$ satisfies \[ e\left( G\right) >\left( 1-\frac{1}{\beta\left( \mathcal{F}\right) -1}+\varepsilon\right) \binom{n}{2}, \] then, by the theorem of Erd\H{o}s and Stone \cite{ErSt46}, $G$ contains a subgraph $G_{0}=K_{\beta}\left( t\right) ,$ that is to say, a complete $\beta$-partite graph with $t$ vertices in each vertex class. Since $K_{r}% \in\mathcal{F}$, we see that $G_{0}$ contains no $K_{r}.$ Hence each vertex class of $G_{0}$ contains an independent set of size $s,$ and so $G$ contains an induced subgraph $K_{\beta}\left( s\right) ,$ which in turn contains an induced copy of $F.$ Thus, if $n$ is large enough and $G\in\mathcal{P}_{n},$ then \[ e\left( G\right) \binom{n}{2}^{-1}\leq1-\frac{1}{\beta\left( \mathcal{F}% \right) -1}+\varepsilon. \] This inequality implies that \[ \pi\left( \mathcal{P}\right) \leq1-\frac{1}{\beta\left( \mathcal{F}\right) -1}, \] completing the proof of Theorem \ref{thpi}. \end{proof} \subsection{Proof of Theorem \protect\ref{thlam}} \begin{proof} First note the inequality \[ \lambda^{\left( p\right) }\left( G\right) \geq2e\left( G\right) /n^{2/p}, \] which follows by taking $\left( x_{1},\ldots,x_{n}\right) =\left( n^{-1/p},\ldots,n^{-1/p}\right) $ in (\ref{maxlam}). So we see that \[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) \geq\pi\left( \mathcal{P}\right) , \] and this inequality together with Theorem \ref{thpi} gives $\lambda^{\left( p\right) }\left( \mathcal{P}\right) =1$ if $\underline{\omega}\left( \mathcal{F}\right) =0,$ and \[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) \geq1-\frac{1}% {\beta\left( \mathcal{F}\right) -1}% \] otherwise. To finish the proof we shall show that% \[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) \leq1-\frac{1}% {\beta\left( \mathcal{F}\right) -1}. \] For this purpose write $k_{r}\left( G\right) $ for the number of $r$-cliques of $G$. Let $F\in\mathcal{F}$ be a complete $\beta$-partite graph, which exists by the definition of $\beta\left( \mathcal{F}\right) ;$ let $s$ be the maximum of the sizes of its vertex classes. Now if $\varepsilon>0$ and $\varepsilon$ is sufficiently small, choose $\delta=\delta\left( \beta,\varepsilon\right) $ as in the Removal Lemma, and set $t=r\left( K_{r},K_{s}\right) ,$ where $r\left( K_{r},K_{s}\right) $ is the Ramsey number of $K_{r}$ vs. $K_{s}.$ If $G\in\mathcal{P}_{n},$ then $K_{\beta}\left( t\right) \nsubseteq G$ for otherwise, as in proof of Theorem \ref{thpi}, we see that $G$ contains an induced copy of $F.$ So if $n$ is large enough Theorem A implies that $k_{\beta}\left( G\right) \leq\delta n^{r}.$ Now, by the Removal Lemma, there is a graph $G_{0}\subset G$ such that $e\left( G_{0}\right) \geq e\left( G\right) -\varepsilon n^{2}$ and $k_{\beta}\left( G_{0}\right) =0.$ For $n$ sufficiently large Propositions \ref{maxlK} and \ref{pro10} imply that \[ \lambda^{\left( p\right) }\left( G\right) \leq\lambda^{\left( p\right) }\left( G_{0}\right) +\left( 2\varepsilon n\right) ^{2-2/p}\leq\left( 1-\frac{1}{\beta-1}\right) n^{2-2/p}+\left( 2\varepsilon n\right) ^{2-2/p}, \] and hence, \[ \lambda^{\left( p\right) }\left( \mathcal{P},n\right) n^{2/p-2}\leq 1-\frac{1}{\beta-1}+\left( 2\varepsilon\right) ^{2-2/p}. \] Since $\varepsilon$ can be chosen arbitrarily small, we see that \[ \lambda^{\left( p\right) }\left( \mathcal{P}\right) \leq1-\frac{1}% {\beta-1}, \] completing the proof of Theorem \ref{thlam}. \end{proof} \section{Concluding remarks} In a sequence of papers the author has shown that many classical extremal results like the Erd\H{o}s-Stone-Bollob\'{a}s theorem \cite{BoEr73}, the Stability Theorem of Erd\H{o}s \cite{Erd66,Erd68} and Simonovits \cite{Sim68}% , and various saturation problems can be strengthened by recasting them for the largest eigenvalue instead of the number of edges; see \cite{Nik11} for an overview and references. The paper \cite{KLM13} and the present note show that some of these edge extremal results can be extended further to $\lambda^{\left( p\right) }\left( G\right) $ for any $p>1.$ A natural challenge here is to reprove all of the above problems by substituting $\lambda^{\left( p\right) }\left( G\right) $ for the number of edges. Theorems \ref{thlim}, \ref{maxlK}, and Proposition \ref{pro10} have been proved in \cite{NikB} for uniform hypergraphs. The streamlined proofs given here are for reader's convenience.\bigskip \subsection*{Acknowledgement} Thanks are due to Bela Bollob\'{a}s and to Alex Sidorenko for useful discussions. \bigskip \begin{thebibliography}{99} \bibitem{Bol98} B. Bollob\'{a}s. \emph{Modern Graph Theory.} Graduate Texts in Mathematics, 184, Springer-Verlag, New York (1998), xiv+394 pp. \bibitem{BoEr73} B. Bollob\'{a}s and P. Erd\H{o}s. On the structure of edge graphs. \emph{J. London Math. Soc.,} 5:317-321, 1973. \bibitem{Erd66} P. Erd\H{o}s. Some recent results on extremal problems in graph theory (Results). In \emph{Theory of Graphs (Internat. Sympos., Rome, 1966)}, pages 117--130. Gordon and Breach, New York; Dunod, Paris, 1967. \bibitem{Erd68} P. Erd\H{o}s. On some new inequalities concerning extremal properties of graphs. In \emph{Theory of Graphs (Proc. Colloq., Tihany, 1966),} pages 77--81. Academic Press, New York, 1968. \bibitem{ErSt46} P. Erd\H{o}s, A.H. Stone. On the structure of linear graphs. \emph{Bull. Amer. Math. Soc.,} 52:1087--1091, 1946. \bibitem{ErSi66} P. Erd\H{o}s and M. Simonovits. A limit theorem in graph theory. \emph{Studia Sci. Math. Hung.} 1:51-57, 1966. \bibitem{KLM13} P. Keevash, J. Lenz, and D. Mubayi. Spectral extremal problems for hypergraphs. \arxiv {1304.0050}. \bibitem{KNS64} G. Katona, T. Nemetz, and M. Simonovits. On a problem of Tur% \'{a}n in the theory of graphs. \emph{Mat. Lapok } 15:228--238, 1964. \bibitem{MoSt65} T. Motzkin and E. Straus. Maxima for graphs and a new proof of a theorem of Tur\'{a}n. \emph{Canad. J. Math.,} 17:533-540, 1965. \bibitem{Nik08} V. Nikiforov. Graphs with many $r$-cliques have large complete $r$-partite subgraphs. \emph{Bull. London Math. Soc.,} 40:23-25, 2008. \bibitem{Nik11} V. Nikiforov. Some new results in extremal graph theory. In \emph{Surveys in Combinatorics, }pages\emph{\ }141--181, Cambridge University Press, 2011. \bibitem{NikB} V. Nikiforov. An analytic theory of extremal hypergraph problems. \arxiv {1305.1073v2}. \bibitem{NikC} V. Nikiforov. Analytic methods for uniform hypergraphs. \arxiv {1308.1654v3}. \bibitem{Sim68} M. Simonovits. A method for solving extremal problems in graph theory, stability problems. In \emph{Theory of Graphs (Proc. Colloq., Tihany, 1966),} pages 279--319, Academic Press, New York, 1968. \bibitem{Sze76} E. Szemer\'{e}di. Regular partitions of graphs. In\emph{\ Colloques Internationaux C.N.R.S.} \emph{No 260 - Probl\`{e}mes Combinatoires et Th\'{e}orie des Graphes,} pages 399-401, Orsay, 1976. \bibitem{Tur41} P. Tur\'{a}n. On an extremal problem in graph theory (in Hungarian). $\emph{Mat.}$ \emph{\'{e}s Fiz. Lapok,} 48:436-452, 1941. \end{thebibliography} \end{document}