Computer Problems in Finding 2-Color Ramsey Numbers

Brian C. Ladd
Assistant Professor of Computer Science
St. Lawrence Unversity

Party Planner Problem

Party Planner Problem

Facebook Problem

• If you're selecting a group from Facebook, what is the least number of people you would have to include to guarantee either three people are mutually acquainted or three people are mutually strangers?

Facebook Problem

• Well studied example in extremal graph theory.
• Given a property, P and a parameter, f on some class of graphs, γ, determine the least integer, n such that

  ∀ G ∈ γ with f(G) ≥ n, P(G) is true

• Facebook Problem: What is the smallest order of a graph such that it contains a clique of size 3 or an anti-clique of size 3?
• R(3, 3) or the Ramsey Number of (3, 3).

Facebook Problem

• If you're selecting a group from Facebook, what is the least number of people you would have to include to guarantee either three people are mutually acquainted or three people are mutually strangers?
• R(3,3) > 5:
  R(3,3) = 6 [Greenwood and Gleason 1955]

Some Results

Computers and Graphs

• Graph representation in a computer
• Adjacency Matrix:

  0 1 2 3 4 0 - 0 1 1 0 1 0 - 0 1 1 2 1 0 - 0 1 3 1 1 0 - 0 4 0 1 1 0 -

No Finesse

• Computer scientists look at the problem, recognizing the exponential growth, and still try brute force.
• To test whether p is R(n, m):
• Enumerate every graph, G of order p
  • Enumerate every subset, s of G's vertices with |s| = n
  • Check if the subgraph induced bys is K_n
• Calculate compliment of G and check for cliques of size m

Our Results

• Using 32-bit integers on ~2001 computers:

  n	m	|G|	# graphs	Runtime
  3	3	6	215	0.15s
  3	4	9	236	72h
  4	4	18	~2175	~5 trillion years

Some Finesse

• Sort nodes by their order. Eliminate from consideration any nodes with order less than n.
• Memoize solutions for smaller graphs
• Divide the workspace and distribute the work