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 Kn 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 Ka, and 2) G contains no Kb. Prove or disprove f(2,3,4) < 106.

The best known upper bound is f(2,3,4) < 3x109. 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?


There were no responses this month. Here are my best upper bounds:

Upper Bounds for f(2,a,b)

a \ b2345678

Upper Bounds for f(3,a,b)

a \ b2345678

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.