List of small integral relation algebras
Compiled by Peter Jipsen
This list is in the order of Roger Maddux's list (see R. Maddux,
The first 198 Relation Algebras, preprint 1993)
The vector <i,j,k> gives the number of identity atoms, symmetric
atoms and nonsymmetric atoms. The total number of atoms is given by
i+j+2k.
The algebras are given by a list of cycles. A cycle xyz
means x;y >= z, and x~ is the converse of x. From this information the
operation table for the atoms can be easily reconstructed. (The cycles
that include the identity atom are not given since they are determined
by the type <i,j,k>.)
If an algebra with 4 atoms or less is nonrepresentable then it is
labeled as such. If no label appears, the algebra is representable
(for 5-atom algebras this information is incomplete). In some cases a
representation in a finite group relation algebra is known and is
given by the name of the group (in GAP 3), the size of the group and
the blocks of group elements that give the atoms of the RA subalgebra
(these were computed using GAP in 1992 and are in a group of minimal
size). For smaller groups these representations were originally
computed by Steve Comer around 1986.
Some of the other representable algebras are known to have no finite
representation, but I am not aware of any that are known to have no
group representation.
A relation algebra is minimal if it generates
a variety of height 2 in the lattice of RA varieties. These algebras
are labeled as "Minimal", and more information about them can be found
in the paper
[1] P. Jipsen and E. Lukacs, Minimal relation
algebras, Algebra Universalis, 32, (1994), 189-203.
Page edited 2006-01-30 (added information computed in '92-'93).
Number of nonisomorphic finite relation algebras with
i = atoms below the identity,
s = symmetric atoms and
n = pairs of nonsymmetric atoms:
<i,s,n> atoms algebras cycles quads perms
---------------------------------------------------
<1,0,0> 1 1 0 0 1
<1,1,0> 2 2 1 0 1
<1,0,1> 3 3 2 1 2
<1,2,0> 3 7 4 0 2
<1,1,1> 4 37 7 8 2
<1,3,0> 4 65 10 3 6
<1,0,2> 5 83 12 29 8
<1,2,1> 5 1316 16 26 4
<1,4,0> 5 3013 20 15 24
<1,1,2> 6 47965 25 73 8
<1,3,1> 6 988464 30 64 12 (Jipsen ~1992)
<1,5,0> 6 3849920 35 45 120 ( " ~1992)
<1,0,3> 7 4492953 38 156 48 ( " ~1992)
<1,2,2> 7 2186435732 44 151 16 ( " 2010-02-05)
<1,4,1> 7 50265788140 50 134 48 ( " 2010-02-07)
<1,6,0> 7 292352449486 56 105 720 ( " 2010-02-08)
<1,1,3> 8 52506245239168 63 291 48 (Fahy/Jipsen 2010-03-24, Maddux 2010-04-23)
<1,3,2> 8 70 278 48
<1,5,1> 8 77 251 240
<1,7,0> 8 84 210 5040
<1,0,4> 9 88 502 384
The entries before <1,2,2> were computed around 1992/93 with a Pascal program
(now at http://math.chapman.edu/~jipsen/relalg/ra/findra.p; compile with
FreePascal from www.freepascal.org using the command fpc findra.p).
Please email additions or corrections to jipsen(AT)chapman(DOT)edu.
1 atom: <1,0,0>
11'1'1'
Z_1 1 ["0"] i.e., Cm(Z_1),
Generates a variety term-equivalent to Boolean algebras
2 atoms: <1,1,0>
1
1'1'1' aa1' Z_2 2 ["0", "1"] i.e., Cm(Z_2)
2
1'1'1' aa1' aaa Z_3 3 ["0", "1 2"]
3 atoms: <1,0,1>
1
aaa~ Z_3 3 ["0", "1", "2"] i.e., Cm(Z_3), Minimal, C_3 in [1]
2
aaa Q countable ["0", "negative rationals", "positive rationals"], Minimal, C_2 in [1]
3
aaa~ aaa Z_7 7 ["0", "1 2 4", "3 5 6"], Minimal, C_1 in [1]
3 atoms: <1,2,0>
1
abb Z_4 4 ["0", "1 3", "2"], Minimal, B_1 in [1]
2
abb aaa Z_6 6 ["0", "1 3 5", "2 4"], Minimal, B_2 in [1]
3
abb bbb Z_6 6 ["0", "1 2 4 5", "3"], Minimal, B_3 in [1]
4
abb aaa bbb Z_9 9 ["0", "1 2 4 5 7 8", "3 6"], Minimal, B_4 in [1]
5
aab abb Z_5 5 ["0", "1 4", "2 3"], Minimal, B_5 in [1]
6
aab abb aaa Z_8 8 ["0", "2 3 5 6", "1 4 7"], Minimal, B_6 in [1]
7
aab abb aaa bbb Z_3xZ_3 9 ["00", "10 20 01 02", "11 22 12 21"], Minimal, B_7 in [1]
4 atoms: <1,1,1> (11 nonrepresentable, 26 representable)
1
abb~ Z_4 4 ["0", "1", "2", "3"] i.e., Cm(Z_4)
2
abb ab~b~ bbb~ Z_6 6 ["0", "1 4", "3", "5 2"]
3
abb ab~b~ bbb~ aaa 3x3 9 ["0", "2 6 4", "1 3 8", "5 7"]
4
abb abb~ ab~b~ aaa Z_12 12 ["0", "1 9 7", "6 2 10 4 8", "11 3 5"]
5
aab bbb~ Z_6 6 ["0", "4", "3 1 5", "2"]
6
aab bbb~ aaa 3x3 9 ["0", "2", "1", "3 6 4 8 5 7"]
7
aab abb abb~ ab~b~ aaa
8
aab abb abb~ ab~b~ bbb~ Nonrepresentable
9
aab abb abb~ ab~b~ bbb~ aaa
10
abb~ bbb~ bbb Q8 8 ["0", "3 5 7", "1", "2 4 6"]
11
abb ab~b~ bbb
12
abb ab~b~ aaa bbb
13
abb ab~b~ bbb~ bbb Z_14 14 ["0", "1 2 11 4 9 8", "7", "13 12 3 10 5 6"]
14
abb ab~b~ bbb~ aaa bbb Z_21 21 ["0","1 2 18 4 16 15 8 9 11","7 14","20 19 3 17 5 6 13 12 10"]
15
abb abb~ ab~b~ aaa bbb Nonrepresentable
16
abb abb~ ab~b~ bbb~ aaa bbb 4x4 16 ["0", "2 6 8 13 15 14", "1 4 5", "3 7 12 9 10 11"]
17
aab bbb
18
aab aaa bbb
19
aab bbb~ bbb Z_14 14 ["0", "2 4 8", "7 1 13 3 11 5 9", "12 10 6"]
20
aab bbb~ aaa bbb Z_21 21 ["0","3 6 12","1 20 2 19 4 17 5 16 7 14 8 13 10 11","18 15 9"]
21
aab abb~ bbb
22
aab abb~ aaa bbb Nonrepresentable
23
aab abb~ bbb~ bbb Nonrepresentable
24
aab abb~ bbb~ aaa bbb Nonrepresentable
25
aab ab~b~ aaa bbb
26
aab abb~ ab~b~ bbb Nonrepresentable
27
aab abb~ ab~b~ aaa bbb Nonrepresentable
28
aab abb~ ab~b~ bbb~ bbb Nonrepresentable
29
aab abb~ ab~b~ bbb~ aaa bbb
30
aab abb ab~b~ bbb Nonrepresentable
31
aab abb ab~b~ aaa bbb
32
aab abb ab~b~ bbb~ bbb Nonrepresentable
33
aab abb ab~b~ bbb~ aaa bbb
34
aab abb abb~ ab~b~ bbb Nonrepresentable
35
aab abb abb~ ab~b~ aaa bbb
36
aab abb abb~ ab~b~ bbb~ bbb Z_21 21 ["0","19 4 16 15 14 12 11","1 20 3 18 8 13","2 17 5 6 7 9 10"]
37
aab abb abb~ ab~b~ bbb~ aaa bbb 7:3 21 ["0","5 7 20 16 19 15 18","1 6 3 4 8 17","2 14 9 10 11 12 13"]
4 atoms: <1,3,0> (20 nonrepresentable, 45 representable)
1
abc
2
abc bcc bbb Z_6 6 ["0", "1 5", "3", "2 4"]
3
abc bbc bcc bbb ccc Z_10 10 ["0", "3 7 4 6", "5", "1 9 2 8"]
4
abc acc bcc aaa bbb ccc
5
abc acc bbc bcc aaa ccc
6
abc acc bbc bcc aaa bbb ccc
7
aac abc bbc ccc D12 12 ["0", "8 10 11", "6 7 9", "3 1 2 4 5"]
8
aac abc acc bbc bcc ccc
9
aac abc acc bbc bcc aaa cccMinimal, B_8 in [1]
10
aac abc acc bbc bcc aaa bbb ccc
11
abb acc bcc 2^3 8 ["0", "6 7", "2 3 4 5", "1"]
12
abb acc bcc aaa 6x2 12 ["0", "9 10 11", "3 6 4 5 7 8", "1 2"]
13
abb acc bcc bbb 6x2 12 ["0", "1 2 10 11", "3 6 4 5 7 8", "9"]
14
abb acc bcc aaa bbb 6x3 18
15
abb acc bcc ccc 6x2 12 ["0", "6 9", "1 2 4 5 7 8 10 11", "3"]
16
abb acc bcc aaa ccc D18 18
17
abb acc bcc bbb ccc 6x3 18
18
abb acc bcc aaa bbb ccc
19
abb abc acc bcc aaa bbb Nonrepresentable
20
abb abc acc bcc aaa bbb ccc Nonrepresentable
21
abb acc bbc bcc Z_10 10 ["0", "1 9 4 6", "5", "2 8 3 7"]
22
abb acc bbc bcc aaa Z_15 15
23
abb acc bbc bcc bbb 8x2 16
24
abb acc bbc bcc aaa bbb
25
abb acc bbc bcc bbb ccc 6x3 18
26
abb acc bbc bcc aaa bbb ccc
27
abb abc acc bbc bcc aaa
28
abb abc acc bbc bcc aaa bbb
29
abb abc acc bbc bcc aaa bbb ccc
30
aac abb abc bcc Z_7 7 ["0", "3 4", "2 5", "1 6"], Minimal, B_9 in [1]
31
aac abb abc bcc aaa Nonrepresentable, Minimal, B_10 in [1]
32
aac abb abc bcc aaa bbb Nonrepresentable, Minimal, B_11 in [1]
33
aac abb abc bcc aaa bbb ccc Nonrepresentable, Minimal, B_12 in [1]
34
aac abb abc bbc bcc Nonrepresentable
35
aac abb abc bbc bcc aaa Nonrepresentable
36
aac abb abc bbc bcc bbb Nonrepresentable
37
aac abb abc bbc bcc aaa bbb Nonrepresentable
38
aac abb abc bbc bcc ccc Nonrepresentable
39
aac abb abc bbc bcc aaa ccc Nonrepresentable
40
aac abb abc bbc bcc bbb ccc 10x2 20
41
aac abb abc bbc bcc aaa bbb ccc Nonrepresentable
42
aac abb acc bbc Z_10 10 ["0", "4 6", "5 1 9 3 7", "2 8"]
43
aac abb acc bbc aaa 8x2 16
44
aac abb acc bbc bbb Z_15 15
45
aac abb acc bbc aaa bbb
46
aac abb acc bbc aaa ccc 6x3 18
47
aac abb acc bbc aaa bbb ccc
48
aac abb abc acc bbc aaa ccc Nonrepresentable
49
aac abb abc acc bbc aaa bbb ccc Nonrepresentable
50
aac abb abc acc bbc bcc Nonrepresentable
51
aac abb abc acc bbc bcc aaa
52
aac abb abc acc bbc bcc bbb Nonrepresentable
53
aac abb abc acc bbc bcc aaa bbb Nonrepresentable (last nonrep 4-atom RA; long proof found in 1993)
54
aac abb abc acc bbc bcc ccc
55
aac abb abc acc bbc bcc aaa ccc
56
aac abb abc acc bbc bcc bbb ccc
57
aac abb abc acc bbc bcc aaa bbb ccc
58
aab aac abb acc bbc bcc Nonrepresentable
59
aab aac abb acc bbc bcc aaa Nonrepresentable
60
aab aac abb acc bbc bcc aaa bbb Nonrepresentable
61
aab aac abb acc bbc bcc aaa bbb ccc
62
aab aac abb abc acc bbc bcc
63
aab aac abb abc acc bbc bcc aaa
64
aab aac abb abc acc bbc bcc aaa bbb
65
aab aac abb abc acc bbc bcc aaa bbb ccc Finite group representation
known from [P. Jipsen, R. D. Maddux and Z. Tuza,
Small representations of the relation algebra
En+1(1, 2, 3), Algebra
Universalis, 33 (1995), 136-139] but probably not the smallest.
5 atoms: <1,0,2> (some nonrepresentability results are known but not included below)
1
aab~ ab~b
2
aaa~ abb ab~b~ bbb~
3
aaa~ abb ab~b~ bbb
4
aaa~ abb ab~b~ bbb~ bbb
5
abb ab~b~ bbb~ aaa
6
aaa~ abb ab~b~ bbb~ aaa
7
abb abb~ ab~b~ aaa
8
abb ab~b~ aaa bbb
9
abb ab~b~ bbb~ aaa bbb
10
aaa~ abb ab~b~ aaa bbb
11
aaa~ abb ab~b~ bbb~ aaa bbb
12
abb abb~ ab~b~ aaa bbb
13
abb abb~ ab~b~ bbb~ aaa bbb
14
abb abb~ ab~b ab~b~ aaa
15
aaa~ abb abb~ ab~b ab~b~ aaa
16
aab~ abb ab~b ab~b~ bbb~ aaa
17
abb abb~ ab~b ab~b~ aaa bbb
18
abb abb~ ab~b ab~b~ bbb~ aaa bbb
19
aaa~ abb abb~ ab~b ab~b~ aaa bbb
20
aaa~ abb abb~ ab~b ab~b~ bbb~ aaa bbb
21
aab aab~ abb abb~ ab~b ab~b~ aaa
22
aab aab~ abb abb~ ab~b ab~b~ bbb~ aaa
23
aaa~ aab aab~ abb abb~ ab~b ab~b~ aaa
24
aaa~ aab aab~ abb abb~ ab~b ab~b~ bbb~ aaa
25
aab aab~ abb abb~ ab~b ab~b~ aaa bbb
26
aab aab~ abb abb~ ab~b ab~b~ bbb~ aaa bbb
27
aaa~ aab aab~ abb abb~ ab~b ab~b~ aaa bbb
28
aaa~ aab aab~ abb abb~ ab~b ab~b~ bbb~ aaa bbb
29
aa~b abb ab~b~ aaa bbb
30
aa~b abb ab~b~ bbb~ aaa bbb
31
aa~b abb abb~ ab~b~ aaa bbb
32
aa~b abb abb~ ab~b~ bbb~ aaa bbb
33
aa~b abb abb~ ab~b ab~b~ aaa bbb
34
aa~b abb abb~ ab~b ab~b~ bbb~ aaa bbb
35
aab aab~ aa~b abb abb~ ab~b ab~b~ aaa
36
aab aab~ aa~b abb abb~ ab~b ab~b~ bbb~ aaa
37
aaa~ aab aab~ aa~b abb abb~ ab~b ab~b~ aaa
38
aaa~ aab aab~ aa~b abb abb~ ab~b ab~b~ bbb~ aaa
39
aab aab~ aa~b abb abb~ ab~b ab~b~ aaa bbb
40
aab aab~ aa~b abb abb~ ab~b ab~b~ bbb~ aaa bbb
41
aaa~ aab aab~ aa~b abb abb~ ab~b ab~b~ aaa bbb
42
aaa~ aab aab~ aa~b abb abb~ ab~b ab~b~ bbb~ aaa bbb
43
aaa~ aab~ aa~b aba abb ab~b~ bbb
44
aab~ aa~b aba abb abb~ ab~b~ bbb
45
aa~b aba abb ab~b~ aaa bbb
46
aa~b aba abb ab~b~ bbb~ aaa bbb
47
aaa~ aa~b aba abb ab~b~ bbb~ aaa bbb
48
aa~b aba abb abb~ ab~b~ aaa bbb
49
aa~b aba abb abb~ ab~b~ bbb~ aaa bbb
50
aab~ aa~b aba abb abb~ ab~b~ aaa bbb
51
aaa~ aab~ aa~b aba abb ab~b ab~b~ bbb~
52
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~
53
aaa~ aab~ aa~b aba abb ab~b ab~b~ bbb~ bbb
54
aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ bbb
55
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ bbb
56
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ bbb
57
aa~b aba abb abb~ ab~b ab~b~ aaa
58
aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa
59
aaa~ aa~b aba abb abb~ ab~b ab~b~ aaa
60
aaa~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa
61
aab~ aa~b aba abb abb~ ab~b ab~b~ aaa
62
aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa
63
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ aaa
64
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa
65
aa~b aba abb abb~ ab~b ab~b~ aaa bbb
66
aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb
67
aaa~ aa~b aba abb abb~ ab~b ab~b~ aaa bbb
68
aaa~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb
69
aab~ aa~b aba abb ab~b ab~b~ aaa bbb
70
aab~ aa~b aba abb ab~b ab~b~ bbb~ aaa bbb
71
aaa~ aab~ aa~b aba abb ab~b ab~b~ bbb~ aaa bbb
72
aab~ aa~b aba abb abb~ ab~b ab~b~ aaa bbb
73
aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb
74
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ aaa bbb
75
aaa~ aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb
76
aaa~ aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~
77
aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb
78
aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ bbb
79
aaa~ aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb
80
aaa~ aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ bbb
81
aab aab~ aa~b aba abb abb~ ab~b ab~b~ aaa bbb
82
aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb
83
aaa~ aab aab~ aa~b aba abb abb~ ab~b ab~b~ bbb~ aaa bbb