A small unavoidable collection of subgraphs

Question

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?

Answer 1

I don't know that this has been studied - but here is one trivial observation. If you have a list of $t$ graphs on $k$ vertices, then the probability that a random $n$-vertex graph contains none as an induced subgraph is at least

$1-t2^{-\binom{k}{2}}n^k$

and it follows that if $n$ is say $2^{k/4}$ then $S(k,n)$ grows exponentially in $k$.

Answer 2

I don't know if this helps, but how about looking at the chromatic number?

Graphs covered by the empty graph

Partition the set of unlabeled graphs with $n$ vertices into classes $\chi_1,\chi_2,\ldots,\chi_n$ such that $G\in \chi_j$ if and only if its chromatic number is $\chi(G)=j$.

Now let $E_i$ be the (empty) graph with $i$ vertices and no edges. If $G\in\chi_j$ and $i\leq \lceil n/j\rceil$, then some colour class has at least $\lceil n/j\rceil$ vertices which induce an empty set.

Back to your question. One way to go about determining $S(k,n)$ is to choose graphs which are induced subgraphs of a large number of $n$-graphs.

Let $\ell$ be such that $k\leq \lceil n/\ell\rceil$. Then $E_k$ is an induced subgraph of any graph $G$ in $\bigcup_{i=1}^\ell \chi_i$.

A second idea

Let $G$ have chromatic number $\chi$, and consider a partition of its vertex set $V(G)$ into classes $V_1,V_2,\ldots V_\chi$ (inducing independent sets) such that $$(|V_1|,|V_2|,\ldots,|V_\chi|)$$ is lexicographically greatest (that is, has greatest first coordinate amongst all colourings; greatest second coordinate among all which have greatest first coordinate; etc.).

Every vertex in $V_{j}$ has a neighbor in $V_i$, for $1\leq i < j$.

Furthermore, if we work under the assumption that $G$ does not contain $E_k$, we know that

$$k > |V_1| \geq |V_2| \geq \cdots \geq |V_\chi|.$$

I hope this is useful. Right now though I am running out of battery and time. Best luck!