On generalized Ramsey numbers

Wai Chee SHIU; Peter Che Bor Lam; Yusheng Li

doi:10.1016/S0012-365X(02)00540-X

On generalized Ramsey numbers

Wai Chee SHIU^*, Peter Che Bor Lam, Yusheng Li

^*Corresponding author for this work

Department of Mathematics

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

1 Citation (Scopus)

5 Downloads (Pure)

Abstract

Let f₁ and f₂ be graph parameters. The Ramsey number r(f₁ m; f₂ ≥ n) is defined as the minimum integer N such that any graph G on N vertices, either f₁(G) ≥ m or f₂(Ḡ) ≥ n. A general existence condition is given and a general upper bound is shown in this paper. In addition, suppose the number of triangles in G is denoted by t(G). We verify that (1 - o(1))(24n)^1/3 ≤ r(t ≥ n; t ≥ n) ≤ (1 + o(1 ))(48n)^1/3 as n → ∞.

Original language	English
Pages (from-to)	X383-388
Journal	Discrete Mathematics
Volume	258
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00540-X
Publication status	Published - 6 Dec 2002

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

User-Defined Keywords

Mixed ramsey number
Ramsey number

Access to Document

10.1016/S0012-365X(02)00540-X

Full Text

Cite this

@article{aead3d16591c4b9bb916bea8f36e3fbd,

title = "On generalized Ramsey numbers",

abstract = "Let f1 and f2 be graph parameters. The Ramsey number r(f1 m; f2 ≥ n) is defined as the minimum integer N such that any graph G on N vertices, either f1(G) ≥ m or f2(Ḡ) ≥ n. A general existence condition is given and a general upper bound is shown in this paper. In addition, suppose the number of triangles in G is denoted by t(G). We verify that (1 - o(1))(24n)1/3 ≤ r(t ≥ n; t ≥ n) ≤ (1 + o(1 ))(48n)1/3 as n → ∞.",

keywords = "Mixed ramsey number, Ramsey number",

author = "SHIU, {Wai Chee} and Lam, {Peter Che Bor} and Yusheng Li",

note = "Funding Information: Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC and a scienti5c foundation of education ministry of China. ∗Corresponding author. E-mail addresses: wcshiu@hkbu.edu.hk (W.C. Shiu), cblam@hkbu.edu.hk (P.C.B. Lam), ysli@hhu.edu.cn (Y. Li).",

year = "2002",

month = dec,

day = "6",

doi = "10.1016/S0012-365X(02)00540-X",

language = "English",

volume = "258",

pages = "X383--388",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - On generalized Ramsey numbers

AU - SHIU, Wai Chee

AU - Lam, Peter Che Bor

AU - Li, Yusheng

N1 - Funding Information: Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC and a scienti5c foundation of education ministry of China. ∗Corresponding author. E-mail addresses: wcshiu@hkbu.edu.hk (W.C. Shiu), cblam@hkbu.edu.hk (P.C.B. Lam), ysli@hhu.edu.cn (Y. Li).

PY - 2002/12/6

Y1 - 2002/12/6

N2 - Let f1 and f2 be graph parameters. The Ramsey number r(f1 m; f2 ≥ n) is defined as the minimum integer N such that any graph G on N vertices, either f1(G) ≥ m or f2(Ḡ) ≥ n. A general existence condition is given and a general upper bound is shown in this paper. In addition, suppose the number of triangles in G is denoted by t(G). We verify that (1 - o(1))(24n)1/3 ≤ r(t ≥ n; t ≥ n) ≤ (1 + o(1 ))(48n)1/3 as n → ∞.

AB - Let f1 and f2 be graph parameters. The Ramsey number r(f1 m; f2 ≥ n) is defined as the minimum integer N such that any graph G on N vertices, either f1(G) ≥ m or f2(Ḡ) ≥ n. A general existence condition is given and a general upper bound is shown in this paper. In addition, suppose the number of triangles in G is denoted by t(G). We verify that (1 - o(1))(24n)1/3 ≤ r(t ≥ n; t ≥ n) ≤ (1 + o(1 ))(48n)1/3 as n → ∞.

KW - Mixed ramsey number

KW - Ramsey number

UR - http://www.scopus.com/inward/record.url?scp=0037032972&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00540-X

DO - 10.1016/S0012-365X(02)00540-X

M3 - Article

AN - SCOPUS:0037032972

SN - 0012-365X

VL - 258

SP - X383-388

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

On generalized Ramsey numbers

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this