Diagonal Ramsey number

The diagonal Ramsey number

R (t)

is the least

n

such that every red-blue edge-colouring of

K_{n}

contains a monochromatic

K_{t}

.

Table of contents
- Binomial upper bound for a Ramsey number Diagonal Ramsey number
- Monochromatic-triangle counting formula Diagonal Ramsey number

Binomial upper bound for a Ramsey number

The off-diagonal recursion

R (s, t) \leq R (s - 1, t) + R (s, t - 1)

with

R (1, t) = R (s, 1) = 1

gives

R (s, t) \leq (s - 1 s + t - 2) .

In particular,

R (t) \leq (t - 1 2 t - 2) < 2^{2 t}

.

Monochromatic-triangle counting formula

In a red-blue edge colouring of

K_{n}

, let

d_{v}

be the red degree of vertex

v

and let

M

be the number of monochromatic triangles. Every nonmonochromatic triangle has exactly two vertices at which its two incident edges have different colors, so

M = (3 n) - \frac{1}{2} \sum_{v} d_{v} (n - 1 - d_{v}) .

Since

d_{v} (n - 1 - d_{v}) \leq ⌊(n - 1)^{2} /4 ⌋

, this identity gives a lower bound for

M

.

 Ancestors (6)

 Incoming links (6)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version