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.


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})$.