What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive search over all unlabeled graphs on n vertices. In my setting, the search can be pruned if I know that a certain induced subgraph on k vertices is forced to occur. For instance, S(3,5)=3 since the set consisting of the empty graph, K3 and one more graph on three vertices is ``unavoidable'' in this sense. Of course, Ramsey's Theorem (specialized to two-colorings of complete graphs) implies that S(k,n)=2 for n sufficiently large, but what happens for smaller values of n? If a set of graphs on k vertices is unavoidable for graphs on n vertices, then it must include both the complete graph and empty graph on k vertices. Finally note that we can replace all the graphs in our set by their complements and obtain another unavoidable set.
It's quite likely this has been studied before. What is the right terminology and what are the earliest references?