0
$\begingroup$

This question is linked to

For a graph $G$, why should one expect the ratio $\text{ex} (n;G)/ \binom n2$ to converge?

where an argument was given that this specific ratio converges for $n\rightarrow\infty$. I would like to find the specific limit in the case where the graph $G$ is the Petersen graph $P$, so want to find $\lim_{n\rightarrow \infty}\text{ex} (n;P)/ \binom n2$

I do not know if there is an explicit formula for $\text{ex} (n;P)$ but if you have any ideas I would be thankful.

$\endgroup$
2
  • 1
    $\begingroup$ I'd rather the question be self-contained; what does ex$(n;P)$ mean? $\endgroup$ Nov 9 '13 at 22:59
  • $\begingroup$ $\text{ex} (n;G)$ is the maximal number of edges of a graph of order $n$ can have without containing $G$ as a subgraph. $\endgroup$
    – Montaigne
    Nov 9 '13 at 23:10
3
$\begingroup$

I think it can be followed from the Erdős–Stone Theorem.

Let $T_r(n)$ denotes the Turán graph, it is a 2-partite Turán-graph with $n$ vertices. Petersen graph has chromatic number 3, i.e the graph cannot be colours with 2 colours $\Rightarrow$ $P\subseteq T_2(n)$ $\forall n\in\mathbb N\rightarrow t_2(n)\le ex(n;P)$ where $t_r(n)$ is the number of edges of $T_r(n)$. Now for sufficiently large $t$ is has to be true that $P\subseteq K_2(t)$ where $K_2(t)$ denotes the complete 2 partite grpah with t vertices.

$\Rightarrow$ $\forall \epsilon >0$ the Erdős–Stone Theorem gives us $ex(n;K_2(t))<t_2(n)+\epsilon n^2$

$\Rightarrow$ For large $n$ we get $t_2(n)/\binom n2\le ex(n;P)/\binom n2\le ex(n;K_2(t))/\binom n2\le t_2(n)/\binom n2+\epsilon n^2/\binom n2\le t_2(n)/\binom n2+4\epsilon$

Now $t_{r-1}(n)/\binom n2$ converges to $\frac{r-2}{r-1}$ and we set $r=3$, i.e the chromatic number of the Petersen grpah it follows that $\lim_{n\rightarrow\infty} ex(n;P)/\binom n2=\frac{3-2}{3-1}=1/2$

In my argumentation we can replace the chromatic number $3$ by any other chromatic number which yields to $\lim_{n\rightarrow\infty} ex(n;G)/\binom n2=\frac{\gamma(G)-2}{\gamma(G)-1}$ where $\gamma(G)$ is the chromatic number of $G$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.