Computing the partition function for cliques in a graph
Alexander I. Barvinok · arXiv (Cornell University) · 2014
We present a deterministic algorithm which, given a graph G with n vertices and an integer 10 is an absolute constant: we can choose gamma=0.06, and if n > 4m and m > 10, we can choose gamma=0.18. This allows us to tell apart the graphs that do not have m-subsets of high density from the graphs that have sufficiently many m-subsets of high density, even when the probability to hit such a subset at random is exponentially small in m.