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

Home

Search

Subjects

About Erdös

About This Site

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

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].