Finding large \(p\)-colored diameter two subgraphs (Q1288513)

Given a colouring of the edges of the complete graph \(K_n\) on \(n\) vertices in \(k\) colours, a \(p\)-coloured subgraph of \(K_n\) is any subgraph whose edges only use colours from some \(p\) element set. It is shown that for \(k\geq 1\) and \(k/2\leq p\leq k\) there is always a \(p\)-coloured diameter two subgraph of \(K_n\) containing at least \((k+p)n/(2k)\) vertices and that this is best possible up to an additive constant \(l\) satisfying \(0\leq l<k/2\).