Description of optimal Cayley graphs found by Marston Conder

From Combinatorics Wiki

Jump to: navigation, search

The generators and orders of some of the optimal graphs in the degree/diameter problem for Cayley graphs. These graphs were found, and shown to be optimal by Marston Conder.

Contents

List of generators for graphs of degree 3

Diameter 2 (Moore bound = 10)

Finitely presented group G on 3 generators, |G| = 8. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2 * G.3 = Id(G)
  G.1 * G.2 * G.1 * G.2^-1 = Id(G)
  G.1 * G.2^4 = Id(G)

Diameter 3 (Moore bound = 22)

Finitely presented group G on 3 generators, |G| = 14. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3^2 = Id(G)
  G.2 * G.1 * G.2 * G.1 * G.2 * G.3 = Id(G)
  G.3 * G.1 * G.2 * G.1 * G.3 * G.1 = Id(G)

Diameter 4 (Moore bound = 46)

Finitely presented group G on 3 generators, |G| = 24. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2 * G.3 = Id(G)
  (G.1 * G.2^2)^2 = Id(G)
  G.1 * G.2 * G.1 * G.2^-5 = Id(G)

Diameter 5 (Moore bound = 94)

Finitely presented group G on 3 generators, |G| = 60. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3^2 = Id(G)
  G.3 * G.2 * G.1 * G.2 * G.1 * G.3 * G.1 * G.3 * G.2 = Id(G)
  (G.1 * G.2)^5 = Id(G)
  G.1 * G.2 * G.3 * G.1 * G.2 * G.1 * G.3 * G.2 * G.1 * G.3 = Id(G)

Diameter 6 (Moore bound = 190)

Finitely presented group G on 3 generators, |G| = 72. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2 * G.3 = Id(G)
  G.2^8 = Id(G)
  G.2^-1 * G.1 * G.2^-3 * G.1 * G.2 * G.1 * G.2^-1 = Id(G)

Diameter 7 (Moore bound = 382)

Finitely presented group G on 3 generators, |G| = 168. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2 * G.3 = Id(G)
  G.2^12 = Id(G)
  G.1 * G.2^-1 * G.1 * G.2^4 * G.1 * G.2^-1 * G.1 * G.2^-2 = Id(G)
  G.2^2 * G.1 * G.2^4 * G.1 * G.2 * G.1 * G.2^-1 * G.1 = Id(G)

List of generators for graphs of degree 4

Diameter 2 (Moore bound = 17)

Finitely presented group G on 4 generators, |G| = 13. Optimal.

Relations: 

  G.1 * G.3 = Id(G)
  G.2 * G.4 = Id(G)
  G.1 * G.2 * G.1^-1 * G.2^-1 = Id(G)
  G.1^3 * G.2^2 = Id(G)
  G.1^-2 * G.2^3 = Id(G)

Diameter 3 (Moore bound = 53)

Finitely presented group G on 4 generators, |G| = 30. Optimal.

Relations: 

  G.1 * G.3 = Id(G)
  G.2 * G.4 = Id(G)
  G.1^-1 * G.2 * G.1^2 * G.2 = Id(G)
  (G.1^2 * G.2^-1)^2 = Id(G)

Diameter 4 (Moore bound = 161)

Finitely presented group G on 4 generators, |G| = 84. Optimal.

Relations: 

  G.1 * G.3 = Id(G)
  G.2 * G.4 = Id(G)
  G.1^6 = Id(G)
  G.2 * G.1 * G.2^-1 * G.1^-1 * G.2 * G.1 * G.2 = Id(G)
  G.1 * G.2^-2 * G.1^-1 * G.2 * G.1^-1 * G.2^-1 = Id(G)

List of generators for graphs of degree 5

Diameter 2 (Moore bound = 26)

Finitely presented group G on 5 generators, |G| = 18. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2 * G.4 = Id(G)
  G.3 * G.5 = Id(G)
  G.2^3 = Id(G)
  (G.1 * G.2)^2 = Id(G)
  G.2 * G.3 * G.2 * G.3^-1 = Id(G)
  G.1 * G.3^-1 * G.2 * G.1 * G.3 = Id(G)
  G.1 * G.3^2 * G.2 * G.3 = Id(G)

Diameter 3 (Moore bound = 106)

Finitely presented group G on 5 generators, |G| = 60. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3^2 = Id(G)
  G.4 * G.5 = Id(G)
  G.1 * G.4 * G.2 * G.4 * G.3 = Id(G)
  G.1 * G.3 * G.2 * G.1 * G.4^2 = Id(G)
  G.1 * G.2 * G.4 * G.2 * G.3 * G.2 = Id(G)
  G.1 * G.3 * G.4^2 * G.3 * G.2 = Id(G)

List of generators for graphs of degree 6

Diameter 2 (Moore bound = 37)

Finitely presented group G on 6 generators, |G| = 32. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3 * G.5 = Id(G)
  G.4 * G.6 = Id(G)
  (G.1 * G.2)^2 = Id(G)
  G.1 * G.3^-1 * G.1 * G.3 = Id(G)
  G.1 * G.4^-1 * G.1 * G.4 = Id(G)
  G.3^-1 * G.2 * G.1 * G.3 * G.2 = Id(G)
  G.4^-1 * G.2 * G.1 * G.4 * G.2 = Id(G)
  G.3^-2 * G.1 * G.3^-2 = Id(G)
  G.4^-1 * G.3^-1 * G.1 * G.4^-1 * G.3^-1 = Id(G)
  G.4 * G.3^-1 * G.1 * G.4 * G.3^-1 = Id(G)
  G.1 * G.4^-4 = Id(G)
  G.2 * G.3^2 * G.4^2 = Id(G)

Diameter 3 (Moore bound = 187)

Finitely presented group G on 6 generators, |G| = 108. Optimal.

Relations: 

   G.3^-1 * G.2^-1 = Id(G)
   G.4^-1 * G.1^-1 = Id(G)
   G.6^-1 * G.5^-1 = Id(G)
   G.2 * G.1^-2 * G.2 * G.5 = Id(G)
   G.5 * G.1^-2 * G.5^-1 * G.1^-1 = Id(G)
   G.5 * G.2^-1 * G.1^-1 * G.2^-1 * G.5 = Id(G)
   G.2 * G.1^3 * G.2^2 = Id(G)

List of generators for graphs of degree 7

Diameter 2 (Moore bound = 50)

Finitely presented group G on 7 generators, |G| = 36. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3^2 = Id(G)
  G.4 * G.6 = Id(G)
  G.5 * G.7 = Id(G)
  (G.1 * G.4)^2 = Id(G)
  (G.2 * G.4)^2 = Id(G)
  (G.3 * G.4)^2 = Id(G)
  G.4^3 = Id(G)
  G.2 * G.4^-1 * G.5^2 = Id(G)
  G.1 * G.2 * G.1 * G.3 * G.4^-1 = Id(G)
  G.3 * G.2 * G.1 * G.2 * G.4 = Id(G)
  G.5^-1 * G.2 * G.1 * G.5 * G.4^-1 = Id(G)

Diameter 3 (Moore bound = 302)

Finitely presented group G on 7 generators, |G| = 168. Optimal.

Relations: 

   G.1^2 = Id(G)
   G.3^-1 * G.2^-1 = Id(G)
   G.5^-1 * G.4^-1 = Id(G)
   G.7^-1 * G.6^-1 = Id(G)
   (G.4 * G.6^-1)^2 = Id(G)
   G.2 * G.1 * G.2^-1 * G.4^-1 * G.6 = Id(G)
   G.2 * G.4^-1 * G.2^-1 * G.6 * G.4 = Id(G)
   G.2 * G.6^-1 * G.2^-1 * G.4 * G.6 = Id(G)
   G.2^6 = Id(G)
   G.6 * G.4^-1 * G.2^2 * G.1 * G.2 = Id(G)

List of generators for graphs of degree 8

Diameter 2 (Moore bound = 65)

Finitely presented group G on 8 generators, |G| = 48. Optimal.

Relations: 

  G.1^2 = Id(G)
  G.2^2 = Id(G)
  G.3^2 = Id(G)
  G.4^2 = Id(G)
  G.5 * G.7 = Id(G)
  G.6 * G.8 = Id(G)
  (G.1 * G.2)^2 = Id(G)
  (G.1 * G.3)^2 = Id(G)
  G.2 * G.3 * G.2 * G.4 = Id(G)
  G.4 * G.3 * G.2 * G.3 = Id(G)
  G.1 * G.5^-1 * G.1 * G.5 = Id(G)
  G.2 * G.5^-1 * G.3 * G.5 = Id(G)
  G.3 * G.5^-1 * G.4 * G.5 = Id(G)
  G.1 * G.6^-1 * G.1 * G.6 = Id(G)
  G.3 * G.2 * G.1 * G.5^-2 = Id(G)
  G.6^-1 * G.2 * G.1 * G.6 * G.2 = Id(G)
  G.6^-1 * G.3 * G.1 * G.6 * G.4 = Id(G)
  G.6^-1 * G.5^-1 * G.1 * G.6 * G.5^-1 = Id(G)
  G.6^-2 * G.1 * G.6^-2 = Id(G)
  G.5 * G.3 * G.2 * G.6^2 = Id(G)

List of generators for graphs of degree 9

Diameter 2 (Moore bound = 82)

Finitely presented group G on 9 generators, |G| = 60. Optimal.

Relations: 

   G.7^2 = Id(G)
   G.3^-1 * G.1^-1 = Id(G)
   G.6^-1 * G.4^-1 = Id(G)
   G.8^-1 * G.2^-1 = Id(G)
   G.9^-1 * G.5^-1 = Id(G)
   (G.1, G.2) = Id(G)
   G.4^-3 = Id(G)
   G.4^-1 * G.5^-1 * G.4^-1 * G.7 = Id(G)
   G.5^-3 = Id(G)
   G.1^-1 * G.7 * G.1 * G.7 = Id(G)
   G.2^-1 * G.7 * G.2 * G.7 = Id(G)
   G.1^-3 * G.2^-1 * G.7 = Id(G)
   G.2 * G.1^-2 * G.4 * G.5^-1 = Id(G)
   G.4 * G.1^-2 * G.5^-1 * G.2 = Id(G)

List of generators for graphs of degree 10

Diameter 2 (Moore bound = 101)

Finitely presented group G on 10 generators, |G| = 72. Optimal.

Relations: 

   G.4^2 = Id(G)
   G.5^2 = Id(G)
   G.9^2 = Id(G)
   G.10^2 = Id(G)
   G.6^-1 * G.2^-1 = Id(G)
   G.7^-1 * G.3^-1 = Id(G)
   G.8^-1 * G.1^-1 = Id(G)
   G.4 * G.1^2 * G.5 = Id(G)
   G.5 * G.1^2 * G.10 = Id(G)
   G.2^3 * G.10 = Id(G)
   (G.2, G.3) = Id(G)
   G.1 * G.4 * G.1^-1 * G.10 = Id(G)
   G.1^-1 * G.9 * G.1 * G.9 = Id(G)
   G.2^-1 * G.9 * G.2 * G.9 = Id(G)
   G.3^-1 * G.9 * G.3 * G.9 = Id(G)
   G.3^-1 * G.10 * G.3 * G.10 = Id(G)
   G.1^-3 * G.2^-1 * G.3^-1 = Id(G)
   G.2 * G.1^-2 * G.3 * G.1 = Id(G)
   G.4 * G.1^-2 * G.9 * G.10 = Id(G)

List of generators for graphs of degree 11

Diameter 2 (Moore bound = 122)

Finitely presented group G on 11 generators, |G| = 84. Optimal.

Relations: 

   G.4^2 = Id(G)
   G.2^-1 * G.1^-1 = Id(G)
   G.8^-1 * G.5^-1 = Id(G)
   G.9^-1 * G.6^-1 = Id(G)
   G.10^-1 * G.7^-1 = Id(G)
   G.11^-1 * G.3^-1 = Id(G)
   (G.1, G.3) = Id(G)
   G.3^-2 * G.1 * G.6^-1 = Id(G)
   G.3^2 * G.1^-1 * G.6 = Id(G)
   G.1^-1 * G.4 * G.1 * G.4 = Id(G)
   G.3^-1 * G.4 * G.3 * G.4 = Id(G)
   G.4 * G.5^-1 * G.4 * G.7^-1 = Id(G)
   G.5^-3 = Id(G)
   G.7 * G.5^-1 * G.4 * G.5^-1 = Id(G)
   G.6^-2 * G.1^-1 * G.6^-1 = Id(G)
   G.1^-3 * G.3 * G.4 = Id(G)
   G.5^-1 * G.1^-2 * G.7^-1 * G.6 = Id(G)
   G.5 * G.1^-2 * G.6 * G.7 = Id(G)

List of generators for graphs of degree 12

Diameter 2 (Moore bound = 145)

Finitely presented group G on 12 generators, |G| = 96. Optimal.

Relations: 

   G.2^2 = Id(G)
   G.6^2 = Id(G)
   G.8^-1 * G.4^-1 = Id(G)
   G.9^-1 * G.7^-1 = Id(G)
   G.10^-1 * G.5^-1 = Id(G)
   G.11^-1 * G.1^-1 = Id(G)
   G.12^-1 * G.3^-1 = Id(G)
   G.1^-3 = Id(G)
   G.4^-1 * G.2 * G.4^-1 = Id(G)
   G.7^-1 * G.2 * G.1 * G.2 = Id(G)
   G.2 * G.3^-1 * G.2 * G.3 = Id(G)
   G.5 * G.3^-1 * G.4^-1 = Id(G)
   G.3^4 = Id(G)
   G.5 * G.4^-1 * G.3^-1 * G.6 = Id(G)
   G.6 * G.4^-1 * G.3^-1 * G.5 = Id(G)
   G.1^-1 * G.6 * G.1 * G.6 = Id(G)
   (G.1 * G.7^-1)^2 = Id(G)
   G.6 * G.7^-1 * G.6 * G.7 = Id(G)
   G.1^-1 * G.2 * G.1^-1 * G.6 * G.7^-1 = Id(G)
   G.1 * G.2 * G.1^-1 * G.5^2 = Id(G)
   G.5^-1 * G.2 * G.1^-1 * G.3^-1 * G.7 = Id(G)
   G.1^-1 * G.3^-1 * G.1^-1 * G.4^-1 * G.7^-1 = Id(G)
Retrieved from "http://combinatoricswiki.org/wiki/Description_of_optimal_Cayley_graphs_found_by_Marston_Conder"