Polychromatic cliques Original Research Article

The sub-Ramsey number sr(Kn,k) is the smallest integer m such that in any edge-colouring of Km which uses every colour at most k times some subgraph Kn has all edges of different colours. It was known that, for a fixed k, the function sr(Kn,k) is O(n3) and Ω(n). We improve these bounds to O(n2) and Ω(n3/2) (slightly less for small values of k).