On generalized Ramsey numbers (Q1850077)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On generalized Ramsey numbers |
scientific article |
Statements
On generalized Ramsey numbers (English)
0 references
2 December 2002
0 references
Let \(f_1\) and \(f_2\) be graphical parameters of positive integers. Let \(m\) and \(n\) be positive integers. Define the Ramsey number \(r(f_1\geq m\); \(f_2\geq n\)) as the least positive integer \(N\) such that for any graph \(G\) of order \(N\) either \(f_1(G)\geq m\) or \(f_2(\overline G)\geq n\). The most natural question is for which pairs \(f_1\), \(f_2\) does \(r(f_1\geq n\); \(f_2\geq m)\) exist. The authors answer this question as well as give a general upper bound. Suppose the number of triangles in a graph \(G\) is denoted \(t(G)\). The authors show that \[ (1- o(1))(24n)^{1/3}\leq r(t(G)\geq n; t(G)\geq n)\leq (1+ o(1))(48n)^{1/3}. \]
0 references