The Clique problem is one of the classical NP complete problems. They are believed to be hard. An equivalent problem is to find the f-vector of a finite simple graph G=(V,E). This means we want to know how many complete subgraphs there are of dimension k. This is called fk and the vector (f0,f1,… ,fd) is the f-vector of G. It defines the f-function f(t) = 1+f0 t+… +fd td+1.
In this paper on parametrized Hopf, we proved the following theorem: given a locally injective function g(x) on the vertex set V of a finite simple graph $G=(V,E)$, then
$f_G(t) = 1+t\sum_{x} f_{S_g(x)}(t)$.
where $S_g(x)$ is part of the unit sphere $S(x)$ where $g(y)$ is smaller than $g(x)$. This is pretty cool as it allows to compute the f-vector recursively using graphs which are in general less than half the size of G leading to a sub-exponential complexity. Of course, there are bad cases close to complete graphs, and where g does not divide unit spheres nicely but they are rare in an Erdoes-Renyi sense. Well, if these bad cases would not exist, then NP=P, which of course is not true (there is no proof for that but nobody believes in NP=P).
When averaging over functions, like averaging over all colorings for a minimal chromatic number, we get the Gauss-Bonnet result
$f_G(t) = 1+\sum_{x} F_{S(x)}(t)$.
where $F_G(t)$ is the anti-derivative of $f_G(t)$.
Here are some slides:
