Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula where you need to run over all conjugacy classes of the symmetric group $S_n$ and the number of conjugacy classes in $S_n$ is the number of partitions of the number $n$ known to behave like $\exp (\sqrt n )$. (There is a famous approximation for the partition function by Hardy and Ramanujan and subsequent expansions.)

Question 1: Is there a better algorithm? Can you improve the number of steps below $\exp (\sqrt n)$?

(Actually, I would be interested also by a different algorithm even if not better.)

While at it:

Question 2 (updated): What is the smallest number of arithmetic operations for an algorithm to count the number of partitions of an integer $n$?

(I asked originally about a better than $\exp (\sqrt n)$ time algorithm for counting the number of partitions of an integer n, but Sasho indicated an $O(n^{3/2}$ algorithm.)

Question 3: Since Questions 1 and 2 are questions with a "tiny input" (a single integer $n$) is computational complexity theory adequate to ask and offer useful answers (reductions etc.) to these (and similar) question?

Question 4: How much better can you do if you want only to approximate the number of isomorphism types by Polya theory or by other means?

Question 5: What is the complexity of sampling precisely or approximately isomorphism types of graphs with $n$ vertices?

Question 6: What is the complexity of questions 1,4,5 if instead of dealing with all graphs on $n$ vertices we deal with subgraphs of an input graph $G$ with $n$ vertices. (This makes these problems ordinary "big input" problems. Here, I am not aware of a $\exp (\sqrt n$) algorithm.

Question 7: Are these problems related in some way to the graph isomorphism problem?

  • 3
    $\begingroup$ Gil, does the following answer Question 2 or did I misunderstand? Euler's pentagonal number theorem gives a recursion for computing the number of partitions $p(n)$ of $n$. $p(n)$ is expressed as an alternating sum of $O(\sqrt{n})$ partition numbers of smaller $n$. This should give a dynamic programming algorithm for $p(n)$ with $O(n^{3/2})$ arithmetic operations. $\endgroup$ Commented Sep 29, 2013 at 4:13
  • 2
    $\begingroup$ Yes this is a very nice idea, and (I suspect there might be even easier ways to do it). Still interesting what's the bast algorithm is. Maybe we can do something like that for graphs??? $\endgroup$
    – Gil Kalai
    Commented Sep 29, 2013 at 5:44
  • 2
    $\begingroup$ In case anyone else was wondering what the known values for the number of graphs for small n are: see oeis.org/A000088 — there are also some asymptotic formulas there that might be relevant for question 4. $\endgroup$ Commented Sep 29, 2013 at 6:47
  • 2
    $\begingroup$ To Question 3: I think the answer is yes. See, for example, P. Bürgisser. On defining integers and proving circuits lower bounds. comput. compl. 18(1):81-103, 2009. doi:10.1007/s00037-009-0260-x. Freely available author's version.) $\endgroup$ Commented Sep 16, 2016 at 5:05
  • 5
    $\begingroup$ To Question 4: how close an approximation do you want? The number of isomorphism types is asymptotically equal to $2^{\binom{n}{2}}/n!$, and in fact is equal to $(1+\varepsilon(n))2^{\binom{n}{2}}/n!$ where $\varepsilon(n) \to 0$ exponentially fast, so just outputting $2^{\binom{n}{2}}/n!$ gives you a very good approximation... $\endgroup$ Commented Mar 8, 2018 at 7:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.