Number of induced \(G\)-subgraphs in a given graph

Problem (proposed by Erdös)

For a graph \(G\), let \(\#(H,G)\) denote the number of induced subgraphs of \(G\) isomorphic to a given graph \(H\).
Determine \[ f(k,n)= \min_G (\#(K_k, G) + \#(K_k, \bar{G})) \] where \(G\) ranges over all graphs on \(n\) vertices and \(\bar{G}\) denotes the complement of \(G\).

An old conjecture of Erdös asserted that a random graph should achieve the minimum (where the order of magnitude for a random graph is \( 2^{1-\binom{k}{2}} \binom{n}{k})\). This, however, was disproved by Thomason. In \( ^{[1]}\), he showed that

\(\displaystyle f(4,n) < \frac 1 {33} \binom{n}{4}, \)

\(\displaystyle f(5,n) < 0.906 \times 2^{1-\binom{5}{2}} \binom {n}{5}, \)

and in general,

\(\displaystyle f(k,n) < 0.936 \times 2^{1-\binom{k}{2}} \binom {n}{k} . \)

Franek and Rödl \( ^{[2]}\) gave a different construction which is simpler but gives a slightly larger constant.

Bibliography
1 A. Thomason, A disproof of a conjecture of Erdös in Ramsey theory, J. London Math. Soc. 39 (1989), 246-255.

2 F. Franek and V. Rödl, \( 2\)-colorings of complete graphs with a small number of monochromatic \( K_4\) subgraphs, Discrete Math. 114 (1993), 199-203.