# Ramsey's Number R(4, 3)

Ramsey's Number R(4, 3) is the least integer N that solves the following problem

In any group of N people either there are 4 that know each other or there are 3 that do not know each other.

Associating the persons in the group with nodes of a graph in which edges join mutual acquaintances the above description could be reformulated as

Any graph with at least R(4, 3) nodes contains either a K_{4} or three pairwise disjoined nodes.

A graph is a pair of sets: a set of nodes and a set of edges. Two graphs are said to be *complementary* if they have the same nodes and disjoined sets of edges whose union consists of all possible edges joing their nodes. Each of the graphs is called a *complement* of the other. The complement of graph G is denoted G^{c}.

We have a third formulation for the Ramsey number R(4, 3):

For a graph G with at least R(4, 3) nodes, either G contains K_{4} or G^{c} contains K_{3}.

Since the relation between complementary graphs is symmetric, R(4, 3) = R(3, 4).

A fourth formulation arises in the study of chromatic graphs. A graph is *n-colored* if its of its edges is uniquely associated with (colored in) one of n colors. A 2-colored graph is called *bichromatic*.

Any bichromatic graph G with at least R(4, 3) nodes, G contains either K_{4} of one color or K_{3} of the other color.

### Proposition 1

R(4, 3) ≤ 10.

### Proof

Choose one of the present fellows - say, A. The rest are split into two groups: those that know A (group S) and those that don't (group T). There are just two possibilities: either

If |S| ≥ 6, then there are 3 members of S that know each other; together with A they form a group of four mutual acquaintances.

If |T| ≥ 4, then either they all know each other (in which case we are done), some two are strangers. In the latter case, together with A these two form a triple of mutual strangers.

A stronger inequality is obtained in a more formal way:

### Proposition 2

R(4, 3) ≤ 9.

### Proof

Observe that both R(3, 3) = 6 and R(4, 2) = 4 are even so that we are in a position to apply the inequality

R(m, n) ≤ R(m-1, n) + R(m, n-1) - 1,

Which gives R(4, 3) ≤ R(3, 3) + R(4, 2) - 1 = 6 + 4 - 1 = 9.

### Theorem

R(4, 3) = 9.

To prove that we need to exhibit a graph with 8 vertices that contains no K_{4} and whose complement contains no K_{3}. Below is one such graph and its complement.

Place 8 nodes on a circle and join all 2- and 3-neighbors. (The immediate neighbor is 1-neighbor, the next is 2-neighbor, and so on.)

For the complement, join each node to its immediate neighbors and to the opposite node.

## References

- V. K. Balakrishnan,
*Theory and Problems of Combinatorics*, Schaum's Outline Series, McGraw-Hill, 1995, pp. 22-25

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny