<p>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.)</p>

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

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

<p>While at it: </p>

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

<p>(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.)</p>

<p><strong>Question 3:</strong> 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?</p>

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

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

<p><strong>Question 6:</strong> 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.</p>

<p><strong>Question 7:</strong> Are these problems related in some way to the graph isomorphism problem?</p>

CC BY-SA 3.0
2013-09-29T04:13:28.163Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-09-29T05:44:06.007Z
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???
Gil Kalai
CC BY-SA 3.0
2013-09-29T06:47:32.597Z
In case anyone else was wondering what the known values for the number of graphs for small n are: see http://oeis.org/A000088 — there are also some asymptotic formulas there that might be relevant for question 4.
David Eppstein
CC BY-SA 3.0
2013-09-30T04:41:25.280Z
Gil, I am thinking about the graph question. BTW, in the comment above I only indicated the number of arithmetic operations, but they will be on very large numbers (requiring $\Theta(\sqrt{n})$ bits to write down), so you probably should expect the algorithm will have actual running time $O(n^2)$.
Sasho Nikolov
CC BY-SA 3.0
2013-10-01T06:04:44.010Z
Sasho, I think that looking at running time in terms of arithmetic operations gives perhaps a sharper view on the problems. For all we know the answer can be as low as logarithmic (for the partitions and graphs) and for the graphs it can be high as exponential (in sqrt n).
Gil Kalai
CC BY-SA 3.0
2016-09-16T05:05:46.547Z
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](http://dx.doi.org/10.1007/s00037-009-0260-x). [Freely available author's version](http://math-www.uni-paderborn.de/agpb/work/6dich.pdf).)
Joshua Grochow
CC BY-SA 3.0
2018-03-08T07:39:05.843Z
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...
Joshua Grochow
CC BY-SA 3.0
2018-03-09T12:46:32.040Z
Dear Joshua, very good point. I suppose It will be desirable to approximate up to exponential or smaller additive error term.
Gil Kalai
CC BY-SA 4.0
2019-05-25T01:08:35.250Z
@GilKalai: I assume for question 5 you want to sample isomorphism types uniformly (since otherwise you just build a random Erdos-Renyi graph...). But for question 6-part-5, do you still want to sample the isomorphism types appearing as subgraphs of $G$ uniformly, or can it now be weighted by how frequently they appear in $G$?
Joshua Grochow
<cc.complexity-theory><graph-theory><graph-algorithms><counting-complexity><graph-isomorphism>
Counting Isomorphism Types of Graphs
Gil Kalai
# Counting Isomorphism Types of Graphs

(Asked by: username_0 on 2013-09-29)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, counting-complexity, graph-isomorphism
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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???  
> **username_2**: In case anyone else was wondering what the known values for the number of graphs for small n are: see http://oeis.org/A000088 — there are also some asymptotic formulas there that might be relevant for question 4.  
> **username_1**: Gil, I am thinking about the graph question. BTW, in the comment above I only indicated the number of arithmetic operations, but they will be on very large numbers (requiring $\Theta(\sqrt{n})$ bits to write down), so you probably should expect the algorithm will have actual running time $O(n^2)$.  
> **username_0**: Sasho, I think that looking at running time in terms of arithmetic operations gives perhaps a sharper view on the problems. For all we know the answer can be as low as logarithmic (for the partitions and graphs) and for the graphs it can be high as exponential (in sqrt n).  
> **username_3**: 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](http://dx.doi.org/10.1007/s00037-009-0260-x). [Freely available author's version](http://math-www.uni-paderborn.de/agpb/work/6dich.pdf).)  
> **username_3**: 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...  
> **username_0**: Dear Joshua, very good point. I suppose It will be desirable to approximate up to exponential or smaller additive error term.  
> **username_3**: @GilKalai: I assume for question 5 you want to sample isomorphism types uniformly (since otherwise you just build a random Erdos-Renyi graph...). But for question 6-part-5, do you still want to sample the isomorphism types appearing as subgraphs of $G$ uniformly, or can it now be weighted by how frequently they appear in $G$?  

---

## 0 answers

