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