Sorry, maybe it was obvious, but I should have been explicit: I'm interested in lower bounds, i.e. results that you can't be less spread than X. --Michael On Sep 25, 2016 8:25 AM, "Michael Kleber" <michael.kleber@gmail.com> wrote:
Suppose you color the edges of K_n with C colors. Say the "spread" of a color = how many of the n vertices are an endpoint of an edge of that color. How small can you make the spread of the most-spread color?
The pigeon-hole principle says you can't get below n/sqrt(k), since you'll have at least n-choose-2 / k edges of some color, and even if you pack them all into a complete subgraph, that's how big it would have to be. But surely you can't force *all* the colors into a really tight complete-graph-like arrangement, so seems like you should be able to improve on that substantially.
Is there terminology for this question? My naive Google searchings are clobbered by the usual kind of edge coloring, where edges of the same color aren't allowed to meet at a vertex, so maybe I'm just looking for the right names to find prior results.
--Michael
-- Forewarned is worth an octopus in the bush.