On a local similarity of graphs

We say that two graphs GG and HH, having the same number of vertices nn, are kk-similar if they contain a common induced subgraph of order kk. We will consider the following question: how large does nn need to be to ensure at least one kk-similar pair in any family of ll graphs on nn vertices? We will present various lower and upper bounds on nn. In particular, we will prove that for l=3l=3, nn equals the Ramsey number R(k,k)R(k,k). Last but not least we will determine the exact values of nn for k=3k=3, k=4k=4 and all ll.