<p>Define the <a href="https://en.wikipedia.org/wiki/Extremal_graph_theory" rel="nofollow noreferrer">extremal Turán function</a> <span class="math-container">$ex(n,G)$</span> of a graph <span class="math-container">$G$</span> as the most edges a graph on <span class="math-container">$n$</span> vertices can have without having a subgraph that is isomorphic to <span class="math-container">$G$</span>. This function is <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem" rel="nofollow noreferrer">known asymptotically</a> if <span class="math-container">$G$</span> is non-bipartite but since it depends on the chromatic number of <span class="math-container">$G$</span>, it is (at least) NP-hard to determine it. For some bipartite graphs the asymptotic/magnitude of <span class="math-container">$ex(n,G)$</span> is also known, but not for all. It is a conjecture that <span class="math-container">$ex(n,G)=\Theta(n^\alpha)$</span> for every <span class="math-container">$G$</span>.</p>

<blockquote>
  <p>Algorithmically, how hard is it to determine <span class="math-container">$ex(n,G)$</span> for an input <span class="math-container">$G$</span>?</p>
</blockquote>

<p>For example, is it decidable whether <span class="math-container">$ex(n,G)=O(n^\alpha)$</span>?</p>

CC BY-SA 4.0
2019-10-11T19:53:09.467Z
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
CC BY-SA 4.0
2019-10-11T21:21:35.950Z
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
CC BY-SA 4.0
2019-10-12T07:02:57.937Z
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
CC BY-SA 4.0
2019-10-12T15:52:11.863Z
@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
CC BY-SA 4.0
2019-11-04T20:39:56.373Z
Here's a somewhat related paper: https://m.tau.ac.il/~nogaa/PDFS/edita.pdf
domotorp
<graph-theory><np-hardness><approximation-hardness><undecidability>
How hard is it to determine ex(n,G)?
domotorp
# How hard is it to determine ex(n,G)?

(Asked by: username_0 on 2019-10-11)

Define the [extremal Turán function](https://en.wikipedia.org/wiki/Extremal_graph_theory) $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](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem) 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)$?

**Tags:** graph-theory, np-hardness, approximation-hardness, undecidability
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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$).  
> **username_2**: 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.  
> **username_0**: @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?  
> **username_0**: Here's a somewhat related paper: https://m.tau.ac.il/~nogaa/PDFS/edita.pdf  

---

## 0 answers

