Cuántos 2-edge-colorantes de $K_n$ hay?

Question

Estoy escribiendo un artículo sobre la Teoría de Ramsey y sería interesante y útil conocer el número de esencialmente diferentes 2-edge-colorantes de $K_n$ hay. Por eso me refiero a que el número de esencialmente diferentes mapas de $\chi:E(K_n)\to\{1,2\}$.

Por supuesto, $2^{\binom{n}{2}-1}$ es un (casi trivial) límite superior pero, habiendo calculado a mano por un par de pequeños valores de $n$, esto es, obviamente, demasiado alto.

He encontrado citado los valores de $n=16$$n=17$, pero eso es prácticamente todo. Supongo, por tanto, que es conocido por todos los valores más pequeños, demasiado, y eso sería más que suficiente para mis propósitos. ¿Alguien sabe explícita de una fórmula o de una "buena" enlazado, o donde podría encontrar tal cosa?

Answer 1

Aún no he tenido tiempo para leer el Clapham papel, pero tal vez puedo ser de uso con una relacionadas con la estadística, el número de no-isomorfo gráficos en $n$ nodos. Hay una gran cantidad de datos sobre este en la OEIS, la secuencia de A000088. Sus dos colores representan básicamente los bordes de encendido y apagado, así que esta es la misma estadística.

Como se puede ver en la OEIS de entrada este es un clásico de la computación, y es sumamente sencilla. Calcular el ciclo de índice del borde de permutación grupo inducida por la $n!$ permutaciones de la permutación de vértices grupo, sustituir con $x+y$ para los bordes de ser encendido y apagado, y la suma de los coeficientes para obtener el número de no-isomorfo gráficos. El ciclo de índice de la permutación de vértices grupo puede ser calculado con un truco que se remonta a 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}).$$ Ahora, con un vértice de permutación en el borde de permutación de la estructura del ciclo de la ex es suficiente, produciendo una reducción de la complejidad, sin la cual estaríamos fuera de suerte. Simplemente examinar y enumerar todos los posibles pares de vértices y de imaginar el movimiento en paralelo (es decir, formando un borde) a lo largo de sus respectivos ciclos hasta el inicio de la configuración que se alcanza. Esto sucede después de la $\operatorname{LCM}(l_1, l_2)$ pasos asumiendo $l_{1,2}$ son las longitudes de los dos ciclos de la permutación de vértices. Hay dos casos cuando los dos vértices de la mentira en el mismo ciclo, dependiendo de si la longitud es par o impar. En el primer caso hay $l/2$ a los pares de retorno a su origen después de la $l/2$ pasos y el resto tome $l$ pasos, donde $l$ es la longitud del ciclo. Por último, hay algunos overcounting a tomar en consideración, en cada ciclo, en el borde de la permutación es overcounted por un factor igual a su longitud. Eso es todo.

Aquí está una lista de valores para que la leyera.

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

El Arce código para calcular estos es como sigue.

con(numtheory);
con(grupo):
con(planta):

pet_cycleind_vrec := 
proc(n)
 local p, s;
 opción de recordar;

 si n=0 entonces devolver 1; fi;

 ampliar(1/n*añadir(a[l]*pet_cycleind_vrec(n-l), l=1..n));
end;

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

 terml := [];

 cf := varp;
 para v en indets(varp) ¿
 d := grado(varp, v);
 terml := [op(terml), seq(v, k=1..d)];
 cf := cf/v^d;
od;

 [cf, terml];
end;


pet_cycleind_edg := 
proc(n)
 opción de recordar;
 local de s, t, res, cycs, l1, l2, planos, u, v;

 si n=0 entonces devolver 1; fi;

 s := 0:
 para t en pet_cycleind_vrec(n) hacer
 plano := pet_flatten_term(t);

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

 para u nops(cycs) ¿
 para v de u+1 a nops(cycs) ¿
 l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
 res := res * [lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
od;
od;

 para u nops(cycs) ¿
 l1 := op(1, cycs[u]);
 si el tipo(l1, impar), entonces
 # [l1]^(1/2*l1*(l1-1)/l1);
 res := res*[l1]^(1/2*(l1-1));
otra cosa
 # [l1/2]^(l1/2/(l1/2))*[l1]^(1/2*l1*(l1-2)/l1)
 res := res*[l1/2]*[l1]^(1/2*(l1-2)); 
fi;
od;

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

s;
end;

pet_varinto_cind :=
proc(poli, ind)
 local subs1, subs2, polyvars, indvars, v, bote, res;

 res := ind;

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

 para v en indvars ¿
 bote := op(1, v);

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

 subs2 := [v=subs(subs1, poli)];

 res := subs(subs2, res);
od;

res;
end;

v :=
proc(n)
 opción de recordar;
 local p, k, gf;

 p := q1+q2;
 gf := expand(pet_varinto_cind(p, pet_cycleind_edg(n)));

 subs({t1=1, t2=1}, gf);
end;

Un cálculo similar se puede utilizar para contar el número binario de relaciones en un conjunto de $n$ elementos y se documenta en este MSE enlace. Este MSE vínculo II muestra cómo enumerar los gráficos que permitan la auto-bucles.

Answer 2

Si buscas en google algo como "clapham más fácil de auto-complemenentary gráficos", se le dar lugar a un documento que enumera la auto-complemementary gráficos. El número de clases de isomorfismo de grafos en $n$ vértices más el número de clases de isomorfismo de auto-complementarios de gráficos es el doble de la cantidad que usted está pidiendo.

Tenga en cuenta que esta enumeración primero fue llevado a cabo por R. C. de Leer, te vas a encontrar la cita en Clapham del papel.