Inverting the Turán problem

inverse-turan_omitted.pdf contains the details of the classification of the extremal graphs for \(\mathcal{E}_{P_3}(k)\) and \(\mathcal{E}_{\{P_3,K_3\}}(k)\).

inverse-turan_check.sage is a \(link(sage)\) file which contains the code to run an exhaustive search to establish the base-case for determining \(\mathcal{E}_{P_3}(k)\). This search implements nauty. The same code is available also as a Sage worksheet: inverse-turan_check.sws.

It turns out that Question 6.1 was answered before we ever even started writing this paper! The results in the paper Large subgraphs without complete bipartite graphs imply that \(\mathcal{E}_{C_4}(k)=\Theta(k^{3/2})\).