I'm writing a paper on Ramsey Theory and it would be interesting and useful to know the number of essentially different 2-edge-colourings of $K_n$ there are. By that I mean the number of essentially different maps $\chi:E(K_n)\to\{1,2\}$.
Of course, $2^{\binom{n}{2}-1}$ is an (almost trivial) upper bound but, having calculated by hand for a few small values of $n$, this is obviously far too high.
I have found quoted values for $n=16$ and $n=17$ but that's pretty much it. I assume, therefore, that it is known for all smaller values, too, and that would be more than adequate for my purposes. Does anyone know of an explicit formula or "good" bound, or where I could find such a thing?
Best Answer
I have not yet had time to read the Clapham paper, but I can perhaps be of use with a related statistic, the number of non-isomorphic graphs on $n$ nodes. There is a wealth of data on this at the OEIS, sequence A000088. Your two colors essentially represent edges being switched on and off, so this is the same statistic.
As you can see from the OEIS entry this is a classic computation, and extremely straightforward. Compute the cycle index of the edge permutation group induced by the $n!$ permutations of the vertex permutation group, substitute with $1+z$ for edges being on and off to get the generating function of non-isomorphic graphs classified by the number of edges. Use Burnside setting all variables to two if only the count rather than a classification is desired. The cycle index of the vertex permutation group can be computed with a trick that goes back to Lovasz: $$ Z(S_0) = 1 \quad \text{and} \quad Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}).$$ Now to turn a vertex permutation into an edge permutation the cycle structure of the former is sufficient, yielding a reduced complexity without which we'd be out of luck. Simply examine and enumerate all possible pairs of vertices and imagine them moving in parallel (i.e., forming an edge) along their respective cycles until the starting configuration is reached. This happens after $\operatorname{LCM}(l_1, l_2)$ steps assuming $l_{1,2}$ are the lengths of the two cycles of the vertex permutation. There are two cases when the two vertices lie on the same cycle, depending on whether the length is even or odd. In the former case there are $l/2$ pairs that return to their origin after $l/2$ steps and the rest take $l$ steps, where $l$ is the length of the cycle. Finally there is some overcounting to take into consideration, as every cycle in the edge permutation is overcounted by a factor equal to its length. That is all.
Here is a list of values to peruse.
The Maple code to compute these is as follows.
Here is the GF of non-isomorphic graphs on five vertices classified by the number of edges:
$${z}^{10}+{z}^{9}+2\,{z}^{8}+4\,{z}^{7}+6\,{z}^{6} +6\,{z}^{5}+6\,{z}^{4}+4\,{z}^{3}+2\,{z}^{2}+z+1.$$
A similar computation can be used to count the number of binary relations on a set of $n$ elements and is documented at this MSE link. This MSE link II shows how to enumerate graphs that permit self-loops.