Inverting the Turán problem

Supplementary materials

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

Notes

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