# Turán number for cubes

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 Turá**n numbers for an \(n\)-cube} (proposed by Erdös and Simonovits[1], 1970)

Let \(Q_k\) denote the \(k\)-cube on \(2^k\) vertices. Determine \(t(n,Q_k)\).In particular, determine \(t(n,Q_3)\).

Erdös and Simonovits[1] proved that

\(\displaystyle t(n,Q_3) \leq c n^{8/5}. \)

An obvious lower bound for \( t(n,Q_3)\) is
\( t(n,C_4) = (\frac 1 2+o(1)) n^{3/2}\). However, no better lower bound than this is known.