Induced subgraphs of given sizes (Q1301633)

This paper considers certain ``natural'' generalizations of ``Turán-type'' extremal problems investigated earlier by \textit{P. Erdős} [Extremal problems in graph theory. Theory Graphs Appl., Proc. Symp. Smolenice 1963, 29-36 (1964; Zbl 0161.20501)] and by \textit{P. Erdős, V. T. Sós}, and the reviewer [Some extremal problems on \(r\)-graphs. New Direct. Theory Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan 1971, 53-63 (1973; Zbl 0258.05132); On the existence of triangulated spheres in \(3\)-graphs, and related problems. Period. Math. Hung. 3, No. 3-4, 221-228 (1973; Zbl 0269.05111)]. An ordered pair \((m,f)\) is said to belong to the spectrum of a graph \(G\) (written \((m,f)\in\text{Sp}(G)\) or \(G\rightarrow(m,f)\)) if there exists in \(G\) an \(m\)-element subset \(M\) of vertices whose induced subgraph has exactly \(f\) edges; an \((m,f)\)-subgraph is then said to be forced; \({\mathcal G}(n,e;m,f)\) denotes the class of \(n\)-vertex \(e\)-edged graphs such that \(G\not\rightarrow(m,f)\). Where \({\mathcal G}(n,e;m,f)=\varnothing\), the authors write \((n,e)\rightarrow(m,f)\); they denote the set \(\{e:(n,e)\rightarrow(m,f)\}\) by \(S(n;m,f)\), and define \(\sigma(m,f):=\limsup_{n\to\infty}\frac{|S(n;m,f)|}{{n\choose 2}}\), which they conjecture ``is actually a limit for all fixed \(m\) and \(f\).'' The set \(\{f:G\rightarrow(m,f)\}\) is denoted by \(\text{Sp}_m(G)\) (cf. \textit{P. Erdős, V. T. Sós} and \textit{R. J. Faudree} [The \(k\)-spectrum of a graph. Graph theory, combinatorics, and algorithms, Vol. 1 (Kalamazoo, MI, 1992), 377-389 (1995; Zbl 0843.05056)]; \textit{R. J. Faudree, R. J. Gould, M. S. Jacobson, J. Lehel}, and \textit{L. M. Lesniak} [Graph spectra. Discrete Math. 150, No. 1-3, 103-113 (1996; Zbl 0862.05053)]). Sections 4 through 7 consider the cases \(f=0\), and \((m,f)=(3,2), (4,3), (5,4)\). ``In Section 8 we give a list of examples for \((m,f)\)-free graphs. The constructions yield upper bounds for \(\sigma(m,f)\) in various ranges of \(m\) and \(f\), we have also some overlapping\(\dots\). Such a combination of constructions yields the main result of this paper (Theorem 1 in \S 9), where we prove that \(\sigma(m,f)\leq\frac 23\) for all but 5 pairs \((m,f)\), (\dots{} for which) we show \(\sigma(m,f)=1\dots\). In \S 10 we summarize the negative examples showing that for fixed \(m\) all but at most 300 pairs \(\sigma(m,f)=0\) in the interval \(0\leq f\leq O(m^{\frac 32})\). Finally, in \S 11, infinitely many pairs are given with \(\sigma(m,f)=\frac 1{12}\)''.