Ramsey number - Revision history

Vipul at 21:57, 29 May 2012

2012-05-29T21:57:37Z

@@ Line 10: / Line 10: @@
 * <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>
+* [[Recurrence relation bound for Ramsey numbers]]: This states that <math>R(m,n) \le R(m - 1,n) + R(m,n-1)</math>. Moreover, if both the numbers <math>R(m - 1,n)</math> and <math>R(m,n - 1)</math> are even, then we get <math>R(m,n) \le R(m - 1,n) + R(m,n-1) - 1</math>
 * [[Binomial coefficient bound for Ramsey numbers]]: This states that <math>R(m,n) \le \binom{m + n - 2}{m - 1}</math>

Vipul at 21:51, 29 May 2012

2012-05-29T21:51:49Z

← Older revision		Revision as of 21:51, 29 May 2012
Line 7:		Line 7:
	==Facts==		==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>		* [[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>		* [[Binomial coefficient bound for Ramsey numbers]]: This states that <math>R(m,n) \le \binom{m + n - 2}{m - 1}</math>

Vipul: /* Facts */

2012-05-29T21:33:56Z

Facts

← Older revision		Revision as of 21:33, 29 May 2012
Line 7:		Line 7:
	==Facts==		==Facts==

	* [[Recurrence relation for Ramsey numbers]]: This states that <math>R(m,n) \le R(m - 1,n) + R(m,n-1)</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>		* [[Binomial coefficient bound for Ramsey numbers]]: This states that <math>R(m,n) \le \binom{m + n - 2}{m - 1}</math>

Vipul: Created page with "==Definition== ===For two parameters=== Suppose $m,n$ are positive integers. The '''Ramsey number''' $R(m,n)$ is defined as the smallest positive integ..."

2012-05-28T18:37:05Z

Created page with "==Definition== ===For two parameters=== Suppose <matH>m,n</math> are positive integers. The '''Ramsey number''' <math>R(m,n)</math> is defined as the smallest positive integ..."

New page

==Definition==

===For two parameters===

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

==Facts==

* [[Recurrence relation 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>

Ramsey number - Revision history

Vipul at 21:57, 29 May 2012

Vipul at 21:51, 29 May 2012

Vipul: /* Facts */

Vipul: Created page with "==Definition== ===For two parameters=== Suppose m,n are positive integers. The '''Ramsey number''' R(m,n) is defined as the smallest positive integ..."

Vipul: Created page with "==Definition== ===For two parameters=== Suppose $m,n$ are positive integers. The '''Ramsey number''' $R(m,n)$ is defined as the smallest positive integ..."