Triangle Ramsey numbers of complete graphs

Jacob Fox; Jonathan Tidor; Shengtong Zhang

doi:10.1016/j.jctb.2025.08.004

Triangle Ramsey numbers of complete graphs

Jacob Fox
, Jonathan Tidor
, Shengtong Zhang

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A graph is H-Ramsey if every two-coloring of its edges contains a monochromatic copy of H. Define the F-Ramsey number of H, denoted by r_F(H), to be the minimum number of copies of F in a graph which is H-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that r_K₃(K_t)=(r(K_t)3) for all sufficiently large t. We do so through a result on graph coloring: there exists an absolute constant K such that every r-chromatic graph where every edge is contained in at least K triangles must contain at least (r3) triangles in total.

Original language	English (US)
Pages (from-to)	268-286
Number of pages	19
Journal	Journal of Combinatorial Theory. Series B
Volume	176
DOIs	https://doi.org/10.1016/j.jctb.2025.08.004
State	Published - Jan 2026

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Graph coloring
Ramsey numbers
Size Ramsey numbers

Access to Document

10.1016/j.jctb.2025.08.004

Cite this

@article{401e672179b74d6baa24bcb3d3e5762e,

title = "Triangle Ramsey numbers of complete graphs",

abstract = "A graph is H-Ramsey if every two-coloring of its edges contains a monochromatic copy of H. Define the F-Ramsey number of H, denoted by rF(H), to be the minimum number of copies of F in a graph which is H-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that rK3(Kt)=(r(Kt)3) for all sufficiently large t. We do so through a result on graph coloring: there exists an absolute constant K such that every r-chromatic graph where every edge is contained in at least K triangles must contain at least (r3) triangles in total.",

keywords = "Graph coloring, Ramsey numbers, Size Ramsey numbers",

author = "Jacob Fox and Jonathan Tidor and Shengtong Zhang",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier Inc.",

year = "2026",

month = jan,

doi = "10.1016/j.jctb.2025.08.004",

language = "English (US)",

volume = "176",

pages = "268--286",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Triangle Ramsey numbers of complete graphs

AU - Fox, Jacob

AU - Tidor, Jonathan

AU - Zhang, Shengtong

PY - 2026/1

Y1 - 2026/1

N2 - A graph is H-Ramsey if every two-coloring of its edges contains a monochromatic copy of H. Define the F-Ramsey number of H, denoted by rF(H), to be the minimum number of copies of F in a graph which is H-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that rK3(Kt)=(r(Kt)3) for all sufficiently large t. We do so through a result on graph coloring: there exists an absolute constant K such that every r-chromatic graph where every edge is contained in at least K triangles must contain at least (r3) triangles in total.

AB - A graph is H-Ramsey if every two-coloring of its edges contains a monochromatic copy of H. Define the F-Ramsey number of H, denoted by rF(H), to be the minimum number of copies of F in a graph which is H-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that rK3(Kt)=(r(Kt)3) for all sufficiently large t. We do so through a result on graph coloring: there exists an absolute constant K such that every r-chromatic graph where every edge is contained in at least K triangles must contain at least (r3) triangles in total.

KW - Graph coloring

KW - Ramsey numbers

KW - Size Ramsey numbers

UR - https://www.scopus.com/pages/publications/105017570947

UR - https://www.scopus.com/pages/publications/105017570947#tab=citedBy

U2 - 10.1016/j.jctb.2025.08.004

DO - 10.1016/j.jctb.2025.08.004

M3 - Article

AN - SCOPUS:105017570947

SN - 0095-8956

VL - 176

SP - 268

EP - 286

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Triangle Ramsey numbers of complete graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this