# How hard is it to determine ex(n,G)?

Define the extremal Turán function $$ex(n,G)$$ of a graph $$G$$ as the most edges a graph on $$n$$ vertices can have without having a subgraph that is isomorphic to $$G$$. This function is known asymptotically if $$G$$ is non-bipartite but since it depends on the chromatic number of $$G$$, it is (at least) NP-hard to determine it. For some bipartite graphs the asymptotic/magnitude of $$ex(n,G)$$ is also known, but not for all. It is a conjecture that $$ex(n,G)=\Theta(n^\alpha)$$ for every $$G$$.

Algorithmically, how hard is it to determine $$ex(n,G)$$ for an input $$G$$?

For example, is it decidable whether $$ex(n,G)=O(n^\alpha)$$?

• Are you talking about simple graphs? If yes, then why it should be undecidable? What's wrong by enumerating over all graphs on n vertices? – Saeed Oct 11 '19 at 19:53
• I'm talking about simple graphs. The problem is that $n$ is not part of the input, but only $G$, so we are looking for a function (of $n$). – domotorp Oct 11 '19 at 21:21
• What kind of description of a function do you want? If you allow the function to be described by an algorithm or program, the answer is easy linear time in $G$: write a program that takes $n$ as input, hardcodes, $G$, and does the brute force search that @Saeed suggests. – David Eppstein Oct 12 '19 at 7:02
• @David Obviously I'm looking for a description that makes sense, but I didn't want to be more precise to allow different solutions. For example, it is a conjecture that $ex(n,G)$ is always $\Theta(n^\alpha)$. Can we determine $\alpha$ if it exists? – domotorp Oct 12 '19 at 15:52
• Here's a somewhat related paper: m.tau.ac.il/~nogaa/PDFS/edita.pdf – domotorp Nov 4 '19 at 20:39