Li rousseau zang 2001 asymptotic upper bounds ramsey functions

../

theorem_2: The bound r(K_k + K̄_l, K_n) ≤ (l + o(1)) n^k/(log n)^(k-1) for fixed k and l, whose case l = 1 is r(k,n) ≤ (1 + o(1)) n^(k-1)/(log n)^(k-2) for every fixed k, the constant 1 + o(1) on the Ajtai–Komlós–Szemerédi upper bound that Problems 166 and 986 record.

---

Yusheng Li, Cecil C. Rousseau and Wenan Zang, Asymptotic Upper Bounds for Ramsey Functions, Graphs and Combinatorics 17 (2001), 123--128, DOI 10.1007/s003730170060 (the running head reads "Graphs and Combinatorics (2001) 17:123--128" with the copyright line "Springer-Verlag 2001"; no issue number is printed, and the DOI is from the publisher's record); the authors at the Department of Mathematics and Physics, Hehai University, Nanjing, the Department of Mathematical Sciences, The University of Memphis, and the Department of Mathematics, The University of Hong Kong (p. 123); received 11 May 1998, final version received 24 March 1999 (p. 128). Footnotes on p. 123 acknowledge support from NSFC 19871023 and the scientific research foundation of the education ministry of China, and from RGC earmarked research grant 338/024/0009 and CRCG research grant 335/024/0010. Cited as [LRZ01] on the problem pages. Its eleven references (pp. 127--128) are Ajtai, Komlós and Szemerédi, A note on Ramsey numbers (1980), the paper's [1], the bounds it sharpens, filed as ajtai_1980_note_ramsey_numbers; Bollobás, Random Graphs (1985), the paper's [2], not held; Bollobás and Erdős, "Oral communication", the paper's [3]; Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), 1--36, the paper's [4], cited for Erdős's 1947 conjecture, filed as chung_1997_open_problems_paul_erdos_graph_theory; Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977), 93, the paper's [5], not held; Erdős and Szekeres, A combinational problem in geometry (1935), as printed, the paper's [6], filed as erdos_1935_combinatorial_problem_geometry; Griggs, An upper bound on the Ramsey numbers $r(3,k)$, J. Comb. Theory Ser. A 35 (1983), 145--153, the paper's [7], not held; Kim, The Ramsey number $r(3,t)$ has order of magnitude $t^2/\log t$ (1995), the paper's [8], filed as kim_1995_ramsey_number_has_order_magnitude; Shearer, A note on the independence number of triangle-free graphs (1983), the paper's [9], the bound Theorem 1 generalizes, filed as shearer_1983_note_independence_number_triangle_free_graphs; Shearer, A note on the independence number of triangle-free graphs, II, J. Comb. Theory Ser. B 53 (1991), 300--307, the paper's [10], not held; and Spencer, Asymptotic lower bounds for Ramsey functions (1977), the paper's [11], filed as spencer_1977_asymptotic_lower_bounds_ramsey_functions. The edition cited is the publisher's version of record; no preprint or later version is known here.

The copy read for this card is the publisher's production PDF: 6 pages, printed pp. 123--128 = PDF pp. 1--6 (printed p. $n$ is PDF p. $n-122$), typeset from the publisher's composition system (3B2 Total Publishing and Acrobat Distiller 4.05 per its metadata, created 12 March 2001), with a text layer that reads the prose cleanly and garbles the mathematics (inequality signs, exponents, subscripts, binomial coefficients and the integrals come out as bare letters and digits, and the font's ligatures print "±" for the en dash and "®" for "fi"). Provenance: the copy was obtained from the publisher on 2026-09-22 as a DRM-free production PDF from https://doi.org/10.1007/s003730170060. The PDF prints "© Springer-Verlag 2001" in the header of its first page (printed p. 123, read on the page image), every other right reserved.

Read status: claims checked for the abstract, the introduction's definitions and recalled bounds (p. 123), the notation $G_v$ and $f_m$, Theorem 1, Theorem 2 and the Lemma (p. 124), the Corollary (p. 125) and the concluding remarks (p. 127), each read clause by clause on the page images of PDF pp. 1--5 on 2026-09-22; the references and the received dates (pp. 127--128, PDF pp. 5--6) were read on the page images. The proof of Theorem 2 (pp. 126--127) was read in full on the page images and its induction and case split were followed; the proofs of the Lemma (pp. 124--125) and of Theorem 1 (pp. 125--126) were read on the page images for structure only, and none of their computations was checked. Nothing here is independently reviewed.

Contents

• Abstract and § 1, Introduction (pp. 123--124, page images). The abstract states the two results: for a graph $G$ on $N$ vertices with average degree $d$ in which every neighborhood induces a subgraph of average degree at most $a$, the independence number is at least $Nf_{a+1}(d)$, with $f_{a+1}(d)=\int_0^1((1-t)^{1/(a+1)})/(a+1+(d-a-1)t)\,dt$; and from this, for fixed $k$ and $l$, $r(K_k+\bar K_l,K_n)\le(l+o(1))n^k/(\log n)^{k-1}$, and in particular $r(K_k,K_n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$. Key words: Ramsey number, Independence number, Average degree, Convex function. Definitions (p. 123): $r(F_1,F_2)$ is the least $N$ such that every graph $G$ on $N$ vertices contains $F_1$ or has $F_2$ in its complement $\bar G$, and $r(k,n)$ abbreviates $r(K_k,K_n)$. Recalled bounds (p. 123): the Erdős--Szekeres bound $r(k,n)\le\binom{n+k-2}{k-1}$ [6]; for fixed $k$ and large $n$, the Ajtai--Komlós--Szemerédi bounds [1] $r(3,n)\le100n^2/\log n$ and $r(k,n)\le(5000)^kn^{k-1}/(\log n)^{k-2}$ for $k\ge4$; Griggs's [7] reduction of the coefficient 100 to 2.4 and Bollobás's [2] of $(5000)^k$ to $2(20)^{k-3}$; and Shearer's [9] $r(3,n)\le(1+o(1))n^2/\log n$ as $n\to\infty$. The authors announce that a special case of their main result gives $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ for $k\ge1$, which improves the earlier bounds when $k\ge4$. The route (p. 123): an upper bound on $r(k,n)$ follows from a lower bound on the independence number of $K_k$-free graphs; Turán gives $\alpha(G)\ge N/(1+d)$, Ajtai, Komlós and Szemerédi give $\alpha(G)\ge N\log d/(100d)$ for triangle-free $G$ (p. 124), and Shearer gives $\alpha(G)\ge Nf(d)$ with $f(x)=(x\log x-x+1)/(x-1)^2\sim(\log x)/x$. The paper's plan is to generalize Shearer's inequality so that it depends on an upper bound for the average degree of every neighborhood subgraph, and to turn that into the improvement of $r(k,n)$ for $k\ge4$. Notation (p. 124): $G_v$ is the subgraph of $G$ induced by the neighborhood of $v$, and $f_m(x)=\int_0^1\frac{(1-t)^{1/m}}{m+(x-m)t}\,dt$.
• Theorem 1 (p. 124, quoted): "Let $G$ be a graph with $N$ vertices and average degree $d$. If for any vertex $v$ of $G$, the average degree of $G_v$ is at most $a$, then $\alpha(G)\ge Nf_{a+1}(d)$." The case $a=0$ (triangle-free $G$, every $G_v$ edgeless) is Shearer's inequality, since $f_1(x)=\int_0^1(1-t)/(1+(x-1)t)\,dt$ is Shearer's $f(x)$; this identification is made here, not in the paper.
• Theorem 2 (p. 124, quoted): "Let $k$ and $l$ be any two fixed integers. Then, as $n\to\infty$, $r(K_k+\bar K_l,K_n)\le(l+o(1))\frac{n^k}{(\log n)^{k-1}}$." Here $K_k+\bar K_l$ is the join of a $k$-clique with $l$ independent vertices; $K_1+\bar K_l=K_{1,l}$ (p. 126) and $K_k+\bar K_1=K_{k+1}$. Paged at theorem_2.
• § 2, The Proofs: the Lemma and the Corollary (pp. 124--125, page images). Lemma (quoted): "For $m\ge1$ and $x\ge0$, the function $f_m(x)=\int_0^1\frac{(1-t)^{1/m}}{m+(x-m)t}\,dt$ satisfies the differential equation $x(x-m)f_m'(x)+(x+1)f_m(x)=1$. (1) Moreover, $f_m(x)$ is completely monotonic on $(0,\infty)$, that is, $(-1)^kf_m^{(k)}(x)\ge0$ for all $k\ge0$ and $x\ge0$. In particular, $f_m$ is positive, decreasing, and convex." Proof (pp. 124--125, structure only): differentiation under the integral and integration by parts give $x(x-m)f_m'(x)=-xf_m(x)+1-f_m(x)$; complete monotonicity "can be seen by repeated differentiating under the integral". Corollary (p. 125, quoted): "The following two statements hold. $f_m(x)\le1/(x+1)$ if $x\le m$; $\ge1/(x+1)$ otherwise. For $m\ge1$, $f_m(x)\ge\int_0^1\frac{(1-t)}{m+(x-m)t},dt =\frac{x\log(x/m)-(x-m)}{(x-m)^2}$." No proof is printed for the Corollary. The closed form is the value of its integral with the natural logarithm, so $\log$ is the natural logarithm throughout the paper; the constant $1+o(1)$ of Theorem 2 and of the concluding remark is read with that base.
• Proof of Theorem 1 (pp. 125--126, page images, structure only). Induction on $N$. If $N\le a+2$ then $d\le a+1$, and Turán's theorem with $1/(d+1)\ge f_{a+1}(d)$ gives the bound; so $N>a+2$ and $d>a+1$. If some vertex has degree $N-1$, Turán on $G_v$ gives $\alpha(G)\ge\alpha(G_v)\ge\frac{N-1}{a+1}\ge\frac N{a+2}=Nf_{a+1}(a+1)\ge Nf_{a+1}(d)$ (2); so the maximum degree is at most $N-2$. With $P(v)=\deg(v)+1$ and $Q(v)$ the number of edges incident with $v$ or a neighbor of $v$, the hypothesis on $G_v$ gives $Q(v)\ge\sum_{vw\in E(G)}\deg(w)-\frac a2\deg(v)$ and an average of $Q$ at least $d^2-ad/2$; the weight $R(v)=1+[P(v)d-2Q(v)]f_{a+1}'(d)-P(v)f_{a+1}(d)$ has average at least $1-d(d-a-1)f_{a+1}'(d)-(d+1)f_{a+1}(d)=0$ "by (1)", so some $v_0$ has $R(v_0)\ge0$ (3). Deleting $v_0$ and its neighbors leaves $H$ with $N-\hat P$ vertices and $Nd/2-\hat Q$ edges; the induction hypothesis, $\alpha(G)\ge1+\alpha(H)$ and the convexity of $f_{a+1}$ (the tangent inequality $f_{a+1}(x)\ge f_{a+1}(d)+f_{a+1}'(d)(x-d)$) give $\alpha(G)\ge Nf_{a+1}(d)$ by (3). The printed step applies the induction hypothesis to $H$ without checking that, for each vertex $u$ of $H$, the graph $H_u$ induced by the neighborhood of $u$ in $H$ has average degree at most $a$; $H_u$ is an induced subgraph of $G_u$, and average degree does not pass to induced subgraphs (a triangle with three isolated vertices has average degree 1, the triangle alone 2). The argument goes through when every $G_v$ has maximum degree at most $a$, a hypothesis $H$ inherits and the one the proof of Theorem 2 supplies (p. 126), so Theorem 2 is unaffected. This observation is made here, not in the paper.
• Proof of Theorem 2 (pp. 126--127, page images, read in full). Induction on $k$. The base $k=1$ is the star $K_1+\bar K_l=K_{1,l}$, for which the paper cites Chvátal's theorem [5], $r(K_{1,l},K_n)=l(n-1)+1$. For the step, with $R(k,l;n)=r(K_k+\bar K_l,K_n)$, take $G$ of order $N=R(k+1,l;n)-1$ with no $K_{k+1}+\bar K_l$ and $\alpha(G)\le n-1$: each vertex has degree at most $R(k,l;n)-1$, and each $G_v$ has maximum, hence average, degree at most $R(k-1,l;n)-1$, so Theorem 1 and the Lemma give $n>\alpha(G)\ge Nf_m(R(k,l;n)-1)\ge Nf_m(R(k,l;n))$ (4) with $m=R(k-1,l;n)$. For $0<\epsilon<1$ the Corollary gives $M$ with $f_m(x)>(1-\epsilon)\log(x/m)/x$ whenever $x/m>M$. The large $n$ are split into the $n'$ with $R(k,l;n')/R(k-1,l;n')>(n')^{1-\epsilon}$ (a parenthesis notes that every large $n$ is an $n'$ when $k=2$) and the $n''$ with the reverse inequality. For $n'$, (4) gives $n'>(1-\epsilon)^2N\log n'/R(k,l;n')$, hence $N\le\frac{n'}{(1-\epsilon)^2}\frac{R(k,l;n')}{\log n'}$, and the bound for $R(k+1,l;n')$ follows from the induction hypothesis on $R(k,l;n')$. For $n''$, $f_m(x)\ge1/(1+x)$ for $x\ge m$ gives $N\le n''[1+R(k,l;n'')]\le n''[1+(n'')^{1-\epsilon}R(k-1,l;n'')]$, and the bound follows from the induction hypothesis on $R(k-1,l;n'')$ because $(n'')^{2-\epsilon}$ is below $(n''/\log n'')^2$ once $n''$ is large. The induction hypothesis is assumed for $1,2,\ldots,k$, and the $n''$ case uses it at $k-1$.
• § 3, Concluding Remarks (p. 127, page image). The section opens with the specialization of the main result, quoted: "for any fixed $k$, $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ as $n\to\infty$", which is Theorem 2 at $l=1$ with $k+1$ written as $k$. It then remarks that at $k=2$ this upper bound is trivially the asymptotic formula; recalls Kim's lower bound $cn^2/\log n$ for $r(3,n)$ [8] and, on the strength of it and the known exact values, states the authors' belief, quoted, "that the asymptotic formula of $r(3,n)$ is $n^2/(\log n)$"; recalls that Bollobás and Erdős [3] asked whether $r(K_1+K_{1,l},K_n)$ really grows linearly in $l$, and poses the same question for the paper's upper bound on $r(K_k+\bar K_l,K_n)$; and records, quoted, that "Erdős [4] conjectured in 1947 that $r(k,n)\ge cn^{k-1}/(\log n)^{c(k)}$" and that Spencer [11] proved $r(k,n)\ge c(n/\log n)^{(k+1)/2}$. The closing remark is that if Erdős's conjecture holds, the proof of Theorem 2 yields $R(k+1,l;n)\le(1+o(1))R(k,l;n)\frac n{\log n}$ as $n\to\infty$. The 1947 conjecture is the statement of Problem 986, in the paper's letters, attributed through Chung's 1997 problem list.
• What the paper does not print. No explicit threshold $n_0$ or rate for the $o(1)$ of Theorem 2 is given; the $o(1)$ depends on $k$ and $l$ and on the $\epsilon$ of the proof. The Corollary carries no proof. The paper gives no lower bound of its own and states no result for $k$ or $l$ growing with $n$.

Compiled scope

The paper is compiled at statement depth for the result the citing problems consume: Theorem 2 (p. 124) with its specialization $l=1$ in the abstract (p. 123) and the concluding remarks (p. 127), read on the page images and paged on theorem_2. Theorem 1, the Lemma and the Corollary are recorded as statements read on the page images; the proof of Theorem 2 was followed, the proofs of the Lemma and Theorem 1 were read for structure only, and nothing here is independently reviewed.

Bears on. #166: the concluding remark (printed p. 127, PDF p. 5), "for any fixed $k$, $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ as $n\to\infty$", at $k=4$ in the paper's letters ($k$ the clique size, $n$ the independent set), is $r(4,n)\le(1+o(1))n^3/(\log n)^2$, in the problem's letters $R(4,k)\le(1+o(1))k^3/(\log k)^2$: the constant $1+o(1)$ on Theorem 6 of Ajtai, Komlós and Szemerédi that the problem page records, the case $l=1$ of Theorem 2 (p. 124), also stated in the abstract (p. 123) as "In particular, $r(K_k,K_n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$". Against Mattheus and Verstraete's lower bound $\Omega(k^3/\log^4k)$ the remaining factor is of order $\log^2k$. #986: the same remark (p. 127) for every fixed $k\ge3$, in the problem's letters $R(s,k)\le(1+o(1))k^{s-1}/(\log k)^{s-2}$, the site's "constant improved to $1+o(1)$" on the Ajtai--Komlós--Szemerédi bound $R(s,k)\ll_sk^{s-1}/(\log k)^{s-2}$. The same paragraph attests the problem's conjecture and its date, "Erdős [4] conjectured in 1947 that $r(k,n)\ge cn^{k-1}/(\log n)^{c(k)}$", citing Chung's 1997 problem list, and quotes Spencer's lower bound as $r(k,n)\ge c(n/\log n)^{(k+1)/2}$.

Results.

• Theorem 2 (p. 124): $r(K_k+\bar K_l,K_n)\le(l+o(1))n^k/(\log n)^{k-1}$ for fixed $k$ and $l$ as $n\to\infty$; at $l=1$, $r(k,n)\le(1+o(1))n^{k-1}/(\log n)^{k-2}$ for every fixed $k$ (abstract, p. 123; concluding remarks, p. 127).

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.