Note on a Ramsey-Turán type problem (Q1073805): Difference between revisions

Let f(n,k,\(\ell)\) be the maximal integer m such that there is a graph on n vertices with m edges, clique number \(<k\), and independence number \(<\ell\). \textit{B. Bollobás} and \textit{P. Erdős} [J. Comb. Theory, Ser. B 21, 166-168 (1976; Zbl 0337.05134)] and independently \textit{E. Szemeredi} [Mat. Lapok 23 (1972), 113-116 (1973; Zbl 0277.05134)] proved that if \(\ell =o(n)\), then \(f(n,4,1\ell)=(1+o(1))n^ 2/8\). Erdős asked the question whether any such graph must contain a K(r,r,r). The author shows that this is not true by proving the existence of a graph with the above properties such that any subgraph on \(\ell\) vertices is the union of a bipartite graph and a forest. Thus, the graph does not have a K(3,3,3).