Xing Peng (安徽大学)
*Long-Tu Yuan (华东师范大学)
Given a family of graphs $\mathcal{L}$, the Tur\'{a}n number ex$(n,\mathcal{L})$ is the maximum possible number of edges in an $n$-vertex $\mathcal{L}$-free graph. The famous Erd\H{o}s-Stone-Simonovits Theorem gives us the asymptotic value of ex$(n,\mathcal{L})$. The famous Erd\H{o}s-Stone-Simonovits Theorem asserts the following: $$\mbox{ex}(n,\mathcal{L})=t_p(n)+o(n^2)=\left(1-\frac{1}{p}\right){n \choose 2}+o(n^2),$$ where $p=\min\{\chi(\mathcal{L}):L\in \mathcal{L}\}-1$ and $t_p(n)$ is the number of edges in a $p$-partite Tur\'{a}n graph. Therefore, if $p(\mathcal{L}) \geq 2$, i.~e., $\mathcal{L}$ does not contain bipartite graphs, then the Erd\H{o}s-Stone-Simonovits Theorem tells us the asymptotic value of ex$(n,\mathcal{L})$. For $p(\mathcal{L}) \geq 2$, in order to determine the exact value of ex$(n,\mathcal{L})$, Simonovits introduced the notion of the decomposition family $\mathcal{M}(\mathcal{L})$ of $\mathcal{L}$. In this paper, we study the Tur\'{a}n number of those families of graphs such that their decomposition families $,\mathcal{M}(\mathcal{L})$ contain a matching and a star. To be precisely, we prove tight bounds on the Tur\'{a}n number of such families of graphs. We note that the upper bound proved in this paper improving upon the following result by Bollob\'as for such families of graphs. For sufficiently large $n$, we have \begin{equation*} t_p(n)+\mbox{ex}(\lceil n/p \rceil,\mathcal{M}(\mathcal{L}))\leq \mbox{ex}(n,\mathcal{L})\leq t_p(n)+(1+o(1))p\cdot \mbox{ex}(n/p,\mathcal{M}(\mathcal{L}))+cn, \end{equation*} In addition, we show the product conjecture by Simonovites is true for special families of graphs.
Math formula preview: