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, 2013 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, 2013 at 23:10

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .