Limit of $\text{ex} (n;P)/ \binom n2$ for the Petersen graph

344 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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$