Given a forbidden graph H and a function f(n), the Ramsey-Turán number RT (n, H, f (n)) is the maximum number of edges of an H-free graph on n vertices with independence number less than f (n). For graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red/blue edge coloring of the complete graph KN contains either a red G or a blue H. Denote G + H by the join graph obtained from disjoint G and H by adding all edges between them completely. We first show that for any fixed graph H, if there are two constants p:= p(H) > 0 and q:= q(H) > 1 such that <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1071_Article_IEq1.gif" Format="GIF" Height="29" Rendition="HTML" Resolution="72" Type="Linedraw" Width="146" /> </InlineMediaObject> <EquationSource Format="TEX">\(R({H,{K_n}}) \le {{p{n^q}} \over {{{({\log n})}^{q - 1}}}}\)</EquationSource> </InlineEquation>, then <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1071_Article_IEq2.gif" Format="GIF" Height="26" Rendition="HTML" Resolution="72" Type="Linedraw" Width="286" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathbf{RT}({n,{K_2} + H,o({{n^{{1 \over q}}}{{({\log n})}^{1 - {1 \over q}}}})}) = o({{n^2}})\)</EquationSource> </InlineEquation>, which extends several previous results. Moreover, we show that for any fixed forest F of order k ≥ 3, and for any 0 < δ < 1 and sufficiently large n<Equation ID="Equa"> <MediaObject> <ImageObject Color="BlackWhite" FileRef="10255_2024_1071_Article_Equa.gif" Format="GIF" Height="27" Rendition="HTML" Resolution="72" Type="Linedraw" Width="280" /> </MediaObject> <EquationSource Format="TEX">\({\mathbf{RT}}({n,F + F,{n^\delta}}) \le {n^{2 - ({1 - \delta})/\lceil {{{({k - 1})({2 - \delta})} \over {1 - \delta}}} \rceil}}.\)</EquationSource> </Equation>As a corollary, we have an upper bound for RT(n, K2,2,2, nδ) for any 0 < δ < 1.

Two Ramsey-Turán Numbers of Small Independence Numbers

期刊论文
发表日期：

2025年10月6日

查看全文

Xin-yu Hu,
Qi-zhong Lin

摘要

Given a forbidden graph H and a function f(n), the Ramsey-Turán number RT (n, H, f (n)) is the maximum number of edges of an H-free graph on n vertices with independence number less than f (n). For graphs G and H, the Ramsey number R(G, H) is the minimum integer N such that any red/blue edge coloring of the complete graph K_N contains either a red G or a blue H. Denote G + H by the join graph obtained from disjoint G and H by adding all edges between them completely. We first show that for any fixed graph H, if there are two constants p:= p(H) > 0 and q:= q(H) > 1 such that \(R({H,{K_n}}) \le {{p{n^q}} \over {{{({\log n})}^{q - 1}}}}\) , then \(\mathbf{RT}({n,{K_2} + H,o({{n^{{1 \over q}}}{{({\log n})}^{1 - {1 \over q}}}})}) = o({{n^2}})\) , which extends several previous results. Moreover, we show that for any fixed forest F of order k ≥ 3, and for any 0 < δ < 1 and sufficiently large n

\({\mathbf{RT}}({n,F + F,{n^\delta}}) \le {n^{2 - ({1 - \delta})/\lceil {{{({k - 1})({2 - \delta})} \over {1 - \delta}}} \rceil}}.\)

As a corollary, we have an upper bound for RT(n, K_2,2,2, n^δ) for any 0 < δ < 1.