16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I haven't thought about this carefully--I'm at the dentist--but it seems to me that it might be easy to apply the Pólya-Burnside-Redfield-Cauchy-Frobenius counting lemma here, since the symmetry group of $K_n$ is so especially simple. $\endgroup$ – MJD Feb 25 '13 at 17:42
  • 1
    $\begingroup$ I do not see how this question can be answered until you explain what you mean by "essentially different". $\endgroup$ – Chris Godsil Feb 25 '13 at 19:58
  • $\begingroup$ Apologies. Two colourings would be "essentially the same" if a relabelling of the vertices of one would give the other, or if they were the same but with the colours switched. (I hesitate to say isomorphic for some reason but that's pretty much what I mean). For example, for a graph of any order, there is only one "essentially different" map that gives colour 1 to precisely one edge and colour 2 to all others. $\endgroup$ – Clum Feb 25 '13 at 20:56
16
$\begingroup$

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 $x+y$ for edges being on and off, and sum the coefficients to get the count of non-isomorphic graphs. 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.

01 1
02 2
03 4
04 11
05 34
06 156
07 1044
08 12346
09 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952
14 29054155657235488
15 31426485969804308768
16 64001015704527557894928
17 245935864153532932683719776
18 1787577725145611700547878190848
19 24637809253125004524383007491432768
20 645490122795799841856164638490742749440
21 32220272899808983433502244253755283616097664
22 3070846483094144300637568517187105410586657814272
23 559946939699792080597976380819462179812276348458981632
24 195704906302078447922174862416726256004122075267063365754368
25 131331393569895519432161548405816890146389214706146483380458576384
26 169487618400693135671278778610295749756246061427513800357039083537927168
27 421260006519643885757174107650953992882782878952295704539600450662355704738816
28 2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
29 18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
30 334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384

The Maple code to compute these is as follows.

with(numtheory);
with(group):
with(combinat):

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*
           add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flatten_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), seq(v, k=1..d)];
        cf := cf/v^d;
    od;

    [cf, terml];
end;


pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;

    if n=0 then return 1; fi;

    s := 0:
    for t in pet_cycleind_symm(n) do
        flat := pet_flatten_term(t);

        cycs := flat[2]; res := 1;

        for u to nops(cycs) do
            for v from u+1 to nops(cycs) do
                l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
                res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
            od;
        od;

        for u to nops(cycs) do
            l1 := op(1, cycs[u]);
            if type(l1, odd) then
                # a[l1]^(1/2*l1*(l1-1)/l1);
                res := res*a[l1]^(1/2*(l1-1));
            else
                # a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
                res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
            fi;
        od;

        s := s + flat[1]*res;
    od;

    s;
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subsl, polyvars, indvars, v, pot;

    polyvars := indets(poly);
    indvars := indets(ind);

    subsl := [];

    for v in indvars do
        pot := op(1, v);

        subs1 :=
        [seq(polyvars[k]=polyvars[k]^pot,
             k=1..nops(polyvars))];

        subsl := [op(subsl), v=subs(subs1, poly)];
    od;

    subs(subsl, ind);
end;

gf :=
proc(n)
option remember;
local gf;

    gf := pet_varinto_cind(1+z, pet_cycleind_edg(n));
    expand(gf);
end;

v :=
proc(n)
option remember;
local cind;

    cind := pet_cycleind_edg(n);

    subs([seq(v=2, v in indets(cind))], cind);
end;

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.

Addendum Jan 11 2017. There is an optimized version of the above which is twice as fast at the following MSE link. Note that we should use Burnside if we only seek the count of these graphs rather than the classification by the number of edges.

$\endgroup$
  • $\begingroup$ Thank you for this. I had not thought to formulate the question in terms of non-isomorphic graphs on $n$ vertices, although it seems so obvious now. Of course, for $n\ge2$, this number is out by one from the figure I'm looking for because the empty graph is the same as the complete graph for my purposes. $\endgroup$ – Clum Mar 19 '13 at 13:23
  • $\begingroup$ On further reflection, this statistic actually gives roughly twice the number of colourings, by symmetry. I'm going to sit and work out the precise relation. $\endgroup$ – Clum Mar 19 '13 at 13:58
  • $\begingroup$ Here is another example where we use the Lovasz formula to calculate the cycle index of the symmetric group. $\endgroup$ – Marko Riedel Oct 28 '13 at 11:46
  • $\begingroup$ This example shows how to enumerate graphs with colored edges when there is in addition to the edge permutation group a group acting on the colors, further reducing the number of equivalence classes. $\endgroup$ – Marko Riedel Dec 18 '13 at 11:02
7
$\begingroup$

If you google on something like "clapham easier self-complementary graphs", you'll be lead to a paper which enumerates self-complementary graphs. The number of isomorphism classes of graphs on $n$ vertices plus the number of isomorphism classes of self-complementary graphs is twice the number you are asking for.

Note that this enumeration was first carried out by R. C. Read; you'll find the citation in Clapham's paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.