On Sep 25, 2016, at 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.
Do you mean "spread of color c" = "number of degree-1 vertices in the subgraph with only color=c edges" ? I was confused by “endpoint”.
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.
You can “dualize” K_n by replacing each edge by a vertex, and joining all n subsets of n-1 of these vertices, corresponding to (former) edges incident on the same (former) vertex, with edges to form K_(n-1)s. I believe the graph problem you want to solve, on the this dual graph, is minimum C-cut. -Veit
--Michael