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 K4 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 Gc.

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 K4 or Gc contains K3.

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 K4 of one color or K3 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 |S| ≥ 6 or |T| ≥ 4. (Otherwise |S∪T| < 9.)

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 K4 and whose complement contains no K3. 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.)

Ramsey number R(4, 3)

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

Ramsey number R(4, 3) - complement

References

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

  1. Ramsey's Theorem
  2. Party Acquaintances
  3. Ramsey Number R(3, 3, 3)
  4. Ramsey Number R(4, 3)
  5. Ramsey Number R(5, 3)
  6. Ramsey Number R(4, 4)
  7. Geometric Application of Ramsey's Theory
  8. Coloring Points in the Plane and Elsewhere
  9. Two Colors - Two Points
  10. Three Colors - Two Points
  11. Two Colors - All Distances
  12. Two Colors on a Straight Line
  13. Two Colors - Three Points
  14. Three Colors - Bichromatic Lines
  15. Chromatic Number of the Plane
  16. Monochromatic Rectangle in a 2-coloring of the Plane
  17. Two Colors - Three Points on Circle
  18. Coloring a Graph
  19. No Equilateral Triangles, Please

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

Copyright © 1996-2017 Alexander Bogomolny

 62315392

Search by google: