# Problem of the Month (November 1999)

This month's problem comes from graph theory. A **graph** is a collection of points (**vertices**) and lines between points (**edges**). The **complete graph** K_{n} is the graph with n vertices with an edge between every two vertices.
Paul Erdös, famous for offering cash awards for unsolved problems, offered $100 for the solution of the following problem:

Let f(c,a,b) denote the smallest integer n for which there is a graph G with n vertices with the properties that: 1) any edge coloring in c colors contains a monochromatic copy of K_{a}, and 2) G contains no K_{b}. Prove or disprove f(2,3,4) < 10^{6}.

The best known upper bound is f(2,3,4) < 3x10^{9}. This problem is really hard, so here is a variation. What if you colored the vertices instead of the edges? Define f(c,a,b) the same way.

For example, the graph below shows that f(2,3,5) ≤ 8. Do you see why?

What bounds can you get on f(c,a,b)? Are all the values of f(c,a,b) finite?

# ANSWERS

There were no responses this month. Here are my best upper bounds:
## Upper Bounds for f(2,a,b)

a \ b | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | - | 5 | 3 | 3 | 3 | 3 | 3 |

3 | - | - | 15 | 8 | 5 | 5 | 5 |

4 | - | - | - | ? | 45 | 15 | 7 |

## Upper Bounds for f(3,a,b)

a \ b | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | - | 14 | 7 | 4 | 4 | 4 | 4 |

3 | - | - | ? | ? | 45 | 17 | 7 |

If you can extend any of these results, please
e-mail me.
Click here to go back to Math Magic. Last updated 11/25/99.