Ramsey number: Difference between revisions

Revision as of 21:51, 29 May 2012

Definition

For two parameters

Suppose $m, n$ are positive integers. The Ramsey number $R (m, n)$ is defined as the smallest positive integer $r$ such that, for any graph whose vertex set has size $r$ , either the clique number is at least $m$ or the independence number is at least $n$ . More explicitly, for any graph whose vertex set has size $r$ , the graph must either contain a $m$ -clique (i.e., $m$ vertices all adjacent to each other) or an independent set of size $n$ ( $n$ vertices no two of which are adjacent to each other).

Facts

Ramsey numbers are symmetric: $R (m, n) = R (n, m)$
$R (m, 1) = R (1, m) = 1$ for all positive integers $m$
$R (m, 2) = R (2, m) = m$ for all positive integers $m$
Recurrence relation bound for Ramsey numbers: This states that $R (m, n) \leq R (m - 1, n) + R (m, n - 1)$
Binomial coefficient bound for Ramsey numbers: This states that $R (m, n) \leq (\binom{m + n - 2}{m - 1})$

@@ Line 7: / Line 7: @@
 ==Facts==
+* [[Ramsey numbers are symmetric]]: <math>R(m,n) = R(n,m)</math>
+* <math>R(m,1) = R(1,m) = 1</math> for all positive integers <math>m</math>
+* <math>R(m,2) = R(2,m) = m</matH> for all positive integers <math>m</math>
 * [[Recurrence relation bound for Ramsey numbers]]: This states that <math>R(m,n) \le R(m - 1,n) + R(m,n-1)</math>
 * [[Binomial coefficient bound for Ramsey numbers]]: This states that <math>R(m,n) \le \binom{m + n - 2}{m - 1}</math>