On the number of distinct induced subgraphs of a graph (Q1117948)

Let \(i(G)\) be the number of pairwise non-isomorphic induced subgraphs of graph \(G=<V,E>\). The graph \(G=<V,E>\) is \(\ell\)-canonical if there is a partition \(<A_i\subset V:\) \(0\leq i<\ell >\) such that \(\{x,y\}\in E\Leftrightarrow \{x',y'\}\in E\) for all \(i,j<1\), \(x,x'\in A\), \(y,y'\in A\). The graph \(G=<V,E>\) is (\(\ell,m)\)-almost canonical if there is an \(\ell\)-canonical graph \(G_0=<V,E_0>\) such that all components of symmetric difference of \(G\) and \(G_0\) (denoted by \(G_{\Delta}G_0=<V,E_{\Delta}E_0>)\) have sizes at most \(m\). The authors and (independently) N. Alon and B. Bollobás prove the following result. Let \(i(G) = o(n^2)\). Then one can omit \(o(n)\) vertices of \(G\) in such a way that the remaining graph is either complete or empty. In the paper the following stronger theorem is proved. Theorem 1. For all \(\epsilon >0\) and for all \(k\geq 1\) there exists a \(\delta >0\) such that for all \(n\) and for all \(G\) with \(n\) vertices \(i(G)\leq \delta n^{k+1}\) it follows that these exists a \(W\subset V\), \(|W| \leq \epsilon n\), such that \(G[V\setminus W]\) is \((\ell,m)\)-almost canonical for some \(\ell\), \(m\) satisfying \(\ell+m\), \(k+1\). In addition the following estimation is obtained. Theorem 2. Let \(G\) be a graph with \(n\) vertices, \(c>0\), \(k > 2c\log 2\) and \(K_{c \log n,c \log n}\not\subset G,\bar G\), where \(K_{n,m}\) is bipartite graph, \(\bar G\) is the complement of \(G\). Then for every sufficiently large \(n\), \(i(G) \geq 2^{n/4k}\).