A combinatorial enumeration problem on graph

149 Views Asked by At

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph?

(You can assume $m\ll n$ and $i\ll m$ if necessary)

Indeed, the number of the subgraphs should not be a precise number since it depends on the way how we delete the edges, but I think the magnitude(i.e. the $\varepsilon$ when write the number as $n^\varepsilon$) is invariant.