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)$?

  • 2
    $\begingroup$ 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? $\endgroup$ – Saeed Oct 11 '19 at 19:53
  • $\begingroup$ 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$). $\endgroup$ – domotorp Oct 11 '19 at 21:21
  • 4
    $\begingroup$ 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. $\endgroup$ – David Eppstein Oct 12 '19 at 7:02
  • $\begingroup$ @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? $\endgroup$ – domotorp Oct 12 '19 at 15:52
  • $\begingroup$ Here's a somewhat related paper: m.tau.ac.il/~nogaa/PDFS/edita.pdf $\endgroup$ – domotorp Nov 4 '19 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.