Abstract:
The talk will be about 4 or 5 theorems which are spinoffs of the following well known anti-Ramsey result: n - 1 is the greatest number of colors that can appear on the edges of the complete graph K(n) in an edge coloring that admits no rainbow K(3) -- meaning a K(3) with all 3 of its edges colored differently. The prettiest of these theorems (in my opinion), due entirely to D.G. Hoffman, is the following: If n > 1 and K(n) is edge-colored so that there is no rainbow K(3), then for at least one color, the edges bearing that color induce a connected spanning subgraph of K(n). Corollary: if n > 1 and t > (n + 1)/2 then there is no "equalized" edge coloring of K(n) which forbids rainbow K(3)'s. (An equalized coloring of any finite collection of things is a coloring in which the color frequencies, meaning the numbers of times the different colors appear, are as nearly equal as possible.)