Number of edges in a graph with small independent sets avoid the octahedron

For a finite family \( {\mathcal F}\) of graphs, let \( t(n, {\mathcal{F}})\) denote the smallest integer \( m\) that every graph on \( n\) vertices and \( m\) edges must contain a member of \( \mathcal{F}\) as a subgraph.

A problem on the octahedron graph (proposed by Erdös, Hajnal, Sós and Szemerédi [1])

Let \(G\) be a graph on \(n\) vertices which contains no \(K_{2,2,2}\) and whose largest independent set has \(o(n)\) vertices. Is it true that the number of edges of \(G\) is \(o(n^2)\)?

Erdös and Simonovits [2] determined the Turán number for the octahedron graph \( K_{2,2,2}\) as well as the other Platonic graphs [3].

1 P. Erdös, A. Hajnal, V. T. Sós and E. Szemerédi, More results on Ramsey-Turán type problems, Combinatorica 3 (1983), 69-81.

2 P. Erdös and M. Simonovits, An extremal graph problem, Acta Math. Acad. Sci. Hungar. 22 (1971/72), 275-282.

3 M. Simonovits, The extremal graph problem of the icosahedron, J. Comb. Theory Ser. B 17 (1974), 69-79.