Conlon 2012 two problems graph ramsey theory

../

theorem_1_2: The induced Ramsey bound with one logarithm in the exponent, the best known upper bound from 2010 until 2025, obtained from pseudo-random hosts.

---

D. Conlon, J. Fox and B. Sudakov, On two problems in graph Ramsey theory, Combinatorica 32 (2012), no. 5, 513--535; DOI 10.1007/s00493-012-2710-3 (printed on p. 513 with the head "Combinatorica 32 (5) (2012) 513--535" and the imprint "Bolyai Society -- Springer-Verlag"; received January 29, 2010; published online 4 October 2012 per the Crossref record read; Mathematics Subject Classification (2000) 05C55, 05D10). Preprint arXiv:1002.0045 (v1 30 January 2010, the only arXiv version; no journal reference on the listing). Cited as [CFS12] on the problem pages.

Two versions of the work were read for this card. The statements of Theorems 1.1, 1.2 and 1.3 and of Lemma 2.5 were compared on the page images of both on 2026-09-22 and are the same in both, word for word; the introduction's recalled results (Erdős--Hajnal, Kohayakawa--Prömel--Rödl, the bipartite bounds of Graham--Rödl--Ruciński, Conlon and Fox--Sudakov) and the concluding remarks were compared in the text layers and match apart from the wording changes listed below. The proofs (Sections 2--3) were not compared. Page numbers in the digest and the result page are the preprint's unless marked "printed"; the page map below converts them. The arXiv record names arXiv's non-exclusive distribution license for the preprint (arXiv:1002.0045), every other right reserved. The published version prints "0209–9683/112/$6.00 © 2012 János Bolyai Mathematical Society and Springer-Verlag" at the foot of its first page (printed p. 513), every other right reserved.

• The preprint copy read for this card is stamped "arXiv:1002.0045v1 [math.CO] 30 Jan 2010", 18 pages with a text layer (the file's metadata names dvips and Ghostscript 9.22 and a 2018 creation date, so it is arXiv's regenerated PDF). It is the canonical version for this card and the version whose page numbers the result page uses. Provenance: the arXiv listing in the source line below; the download date was not recorded and precedes this card's creation on 2026-09-04; 232,557 bytes. - The published version read for this card is the publisher's production PDF of Combinatorica 32 (2012), 513--535: 23 pages, printed pp. 513--535 = PDF pp. 1--23 (printed p. $n$ is PDF p. $n-512$), typeset from TeX (LaTeX with hyperref and Acrobat Distiller 9.4.2 per the file's metadata, created 16 December 2012), with a clean text layer that reads the prose and garbles only the stacked displays. Provenance: obtained from the publisher on 2026-09-22 as a DRM-free production PDF, from https://doi.org/10.1007/s00493-012-2710-3; 305,806 bytes.

Page map (preprint page, then printed page of the published version): title and abstract, p. 1 = p. 513; the Burr--Erdős problem and the bounds of Eaton and of Graham, Rödl and Ruciński, p. 2 = p. 514; the bipartite recalls, Theorem 1.1, the definition of $r_{\mathrm{ind}}(H)$, Erdős's conjecture, the Erdős--Hajnal and Kohayakawa--Prömel--Rödl bounds and Theorem 1.2, pp. 2--3 = p. 515; pseudo-randomness and Theorem 1.3, p. 3 = p. 516; the method and the conventions, p. 3 = p. 517; Section 2, pp. 4--8 = pp. 517--523, with Lemma 2.5 on p. 6 = p. 521; Section 3, pp. 8--15 = pp. 523--532; Section 4, Concluding remarks, pp. 15--16 = pp. 532--533; references [1]--[36], pp. 16--18 = pp. 533--535.

Wording changes seen in the comparison, none of them substantive: the published abstract (p. 513) reads "there are positive constants" for the bounds of Graham, Rödl and Ruciński where the preprint's p. 1 reads "there are constants"; the published p. 515 reads "an induced subgraph of $G$" where the preprint's p. 2 misprints "an induced subgraph of $H$", and says that Kohayakawa, Prömel and Rödl "proved that there is a constant" where the preprint's p. 2 says "there was"; the published p. 516 says $G(N,p)$ "is with high probability a $(p,\lambda)$-pseudo-random graph" where the preprint's p. 3 says "is itself"; the published p. 533 adds "($q\ge3$)" to the $q$-color remark. The published version numbers its statements "Theorem 1.1." with a period and sets them in italics.

The published version contains no theorem beyond Sections 1--3. Its Section 4 (pp. 532--533) is the concluding remarks of the preprint (arrangeability, degeneracy and the Burr--Erdős conjecture, the Ramsey number of graphs with $m$ edges and Sudakov's proof of Erdős's conjecture, the $q$-color case), with no numbered statement; a search of its text layer finds no "Theorem 4", no "$d+6$" and no hypercube; "bipartite" occurs only in the introduction's recalls of other authors' bounds (pp. 514--515), once in a proof on p. 531 and in reference titles (pp. 533--535). The bound $r(H)\le2^{\Delta+6}n$ for bipartite $H$ on $n$ vertices with maximum degree $\Delta$, with $r(Q_d)\le2^{2d+6}$, which Problem 181's sources quote as "[4, Theorem 4.1]" of Conlon, Fox and Sudakov, is Theorem 4.1 and Corollary 4.2 of the same authors' Short proofs of some extremal results II (J. Combin. Theory Ser. B 121 (2016), 173--196), filed as conlon_2016_short_proofs_extremal_results_ii; that paper is what Tikhomirov's reference [4] and Lee's reference [11] name (read in the reference lists of their preprints). It is not in this paper in either version.

Read status: claims checked for Theorems 1.1, 1.2 and 1.3 (preprint pp. 2--3) and Lemma 2.5 (p. 6), read clause by clause on the page images of the preprint on 2026-09-17, and again on the page images of the published version's pp. 513--516 (title page, introduction, the three theorems), 521 (Lemma 2.5) and 532--533 (Section 4) on 2026-09-22; the rest of the published version (pp. 517--531 and 533--535) was read in the text layer for structure and for the search recorded above. No proof was read in either version.

The paper attacks two classical questions with one method built on pseudo-random and bi-dense host graphs together with an embedding lemma (Lemma 2.5). Theorem 1.1 improves the bound of Graham, Rödl and Ruciński for bounded-degree Ramsey numbers from c(Delta) <= 2^{c Delta log^2 Delta} to c(Delta) <= 2^{c Delta log Delta}, so r(H) <= 2^{c Delta log Delta} n for every n-vertex graph H of maximum degree Delta, moving closer to the lower bound 2^{c' Delta}. Theorem 1.2 shows every n-vertex graph H has induced Ramsey number r_ind(H) <= 2^{c n log n}, improving Kohayakawa, Prömel and Rödl by a factor log n in the exponent and coming a step nearer to Erdős's conjectured 2^{cn}. Theorem 1.3 is the underlying general statement: in any (1/2, lambda)-pseudo-random graph on N vertices with lambda <= 2^{-c n log n} N, every n-vertex graph appears as an induced monochromatic copy in every 2-coloring, all in the same color. For Problem 565, which asks whether the induced Ramsey number of an n-vertex graph is at most 2^{cn}, this was the best upper bound before the exponential bound of 2025 (Aragão, Campos, Dahia, Filipe and Marciano).

Contents

• Introduction (p. 2 = printed pp. 514--515): the Burr--Erdős problem $r(H)\le c(\Delta)n$; the Chvátal--Rödl--Szemerédi--Trotter tower-type $c(\Delta)$; Eaton's $2^{2^{c\Delta}}$; Graham, Rödl and Ruciński's $2^{c\Delta\log^2\Delta}$ and their bipartite $2^{c\Delta\log\Delta}n$ with the lower bound $2^{c'\Delta}n$; the bipartite $2^{c\Delta}n$ of Conlon and of Fox and Sudakov, recalled as "essentially best possible"; the definition of $r_{\mathrm{ind}}(H)$; existence by Deuber, Erdős--Hajnal--Pósa and Rödl; Erdős's conjecture $r_{\mathrm{ind}}(H)\le2^{cn}$, best possible by the complete graph; the Erdős--Hajnal bound $2^{2^{n^{1+o(1)}}}$ stated in a problem paper of Erdős; Kohayakawa, Prömel and Rödl's $2^{cn\log^2n}$.
• Theorem 1.1 (p. 2 = printed p. 515): "There exists a constant $c$ such that, for every graph $H$ with $n$ vertices and maximum degree $\Delta$, $r(H)\le2^{c\Delta\log\Delta}n$."
• Theorem 1.2 (p. 3 = printed p. 515): "There exists a constant $c$ such that every graph $H$ with $n$ vertices satisfies $r_{\mathrm{ind}}(H)\le2^{cn\log n}$."
• Theorem 1.3 (p. 3 = printed p. 516): "There exists a constant $c$ such that, for any $n\in\mathbb N$ and any $(\frac12,\lambda)$-pseudo-random graph $G$ on $N$ vertices with $\lambda\le2^{-cn\log n}N$, every graph on $n$ vertices occurs as an induced monochromatic copy in all 2-edge-colorings of $G$. Moreover, all of these induced monochromatic copies can be found in the same color." Theorem 1.2 follows by applying it to $G(N,1/2)$ or to the Paley graph $P_N$ (p. 3 = printed p. 516).
• Lemma 2.5 (p. 6 = printed p. 521): "If $\rho\le1/30$ and $G$ is a graph on $N\ge4(2/\rho)^{2\Delta}\alpha^{-1}n$ vertices which is $(\alpha,\frac1{2\Delta},\rho,\Delta)$-dense, then $G$ contains every graph $H$ on $n$ vertices with maximum degree at most $\Delta$."
• Conventions (p. 3 = printed p. 517): floors and ceilings omitted; logarithms to the base 2.
• Section 4, Concluding remarks (pp. 15--16 = printed pp. 532--533): recalled results of others and open questions, as recorded above; no numbered statement and no new result.

Compiled scope

Pages 1--3 and 6 of the preprint and printed pp. 513--516, 521 and 532--533 of the published version were read on the page images; the proofs (Sections 2--3) were not read. Nothing here is independently reviewed.

Source: https://arxiv.org/abs/1002.0045.

Bears on. #565: Theorem 1.2 (printed p. 515, PDF p. 3 of the published version; preprint p. 3), "There exists a constant $c$ such that every graph $H$ with $n$ vertices satisfies $r_{\mathrm{ind}}(H)\le2^{cn\log n}$", is the refereed $2^{O(n\log n)}$ bound the site records as the last step before the exponential bound; it is history on the problem page. #181: negative bearing only. The paper contains no bound on $r(Q_n)$ and no bipartite theorem of its own; Theorem 1.1 (printed p. 515) is its bounded-degree bound $r(H)\le2^{c\Delta\log\Delta}n$, which for $Q_n$ ($\Delta=n$, $2^n$ vertices) gives only $r(Q_n)\le2^{cn\log n+n}$, weaker than the bounds the problem page records. The prior bound $r(Q_n)\le2^{2n+6}$ that the problem page once attributed to this paper is Corollary 4.2 of the 2016 paper linked above.

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