This page contains some data relating to semigroups and transformations.
The files on this page are available gzipped and
xzipped since the latter provides better
compression in some cases. The transformations are encoded using
the Semigroups package for
GAP, as described
here, and they can be extracted using the function
ReadGenerators as described
here.
Transformations...
...up to conjugation
The transformations up to conjugation (by elements of the symmetric group) of degrees 2 to 20 can be found below. The representatives with the lex-least image lists are given.
The transformations of degrees 11 to 20 were produced using geng
from nauty, and their lex-least
image lists were found by Chris Jefferson.
Thanks go to Brendan McKay for explaining how to use geng, and to Chris for finding the lex-least images.
The sequence of numbers of transformations up to conjugation is A001372 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 3 | 34.0B | 72.0B |
| 3 | 7 | 48.0B | 88.0B |
| 4 | 19 | 76.0B | 120.0B |
| 5 | 47 | 133.0B | 180.0B |
| 6 | 130 | 292.0B | 316.0B |
| 7 | 343 | 727.0B | 596.0B |
| 8 | 951 | 2.0K | 1.1K |
| 9 | 2,615 | 5.8K | 2.4K |
| 10 | 7,318 | 18.8K | 6.5K |
| 11 | 20,491 | 60.2K | 43.0K |
| 12 | 57,903 | 171.4K | 119.3K |
| 13 | 163,898 | 491.5K | 330.6K |
| 14 | 466,199 | 1.4M | 919.4K |
| 15 | 1,328,993 | 4.0M | 2.6M |
| 16 | 3,799,624 | 11.4M | 7.6M |
| 17 | 10,884,049 | 32.7M | 21.7M |
| 18 | 31,241,170 | 94.2M | 62.1M |
| 19 | 89,814,958 | 275.9M | 177.8M |
| 20 | 258,604,642 | 809.7M | 512.0M |
...up to conjugation and connected
The connected transformations up to conjugation (by elements of the symmetric group) of degrees 2 to 20 can be found below. The representatives with the lex-least image lists are given for those transformations of degree 2 to 10 but not for degrees 11 to 20.
The sequence of numbers of connected transformations up to conjugation is A002861 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 2 | 92.0B | 164.0B |
| 3 | 4 | 39.0B | 80.0B |
| 4 | 9 | 53.0B | 92.0B |
| 5 | 20 | 77.0B | 116.0B |
| 6 | 51 | 134.0B | 172.0B |
| 7 | 125 | 268.0B | 268.0B |
| 8 | 329 | 673.0B | 420.0B |
| 9 | 862 | 1.7K | 1.0K |
| 10 | 2,311 | 5.6K | 2.5K |
| 11 | 6,217 | 19.4K | 13.0K |
| 12 | 16,949 | 52.6K | 33.0K |
| 13 | 46,350 | 143.9K | 85.3K |
| 14 | 127,714 | 395.8K | 227.3K |
| 15 | 353,272 | 1.1M | 596.7K |
| 16 | 981,753 | 3.0M | 1.5M |
| 17 | 2,737,539 | 8.2M | 4.2M |
| 18 | 7,659,789 | 22.9M | 11.8M |
| 19 | 21,492,286 | 65.0M | 32.3M |
| 20 | 60,466,130 | 183.0M | 93.2M |
...up to conjugation and disconnected
The disconnected transformations up to conjugation (by elements of the symmetric group) of degrees 2 to 20 can be found below. The representatives with the lex-least image lists are given for those transformations of degree 2 to 10 but not for degrees 11 to 20.
The sequence of numbers of disconnected transformations up to conjugation is A127912 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 1 | 84.0B | 156.0B |
| 3 | 3 | 35.0B | 76.0B |
| 4 | 10 | 60.0B | 100.0B |
| 5 | 27 | 99.0B | 148.0B |
| 6 | 79 | 207.0B | 244.0B |
| 7 | 218 | 497.0B | 456.0B |
| 8 | 622 | 1.4K | 860.0B |
| 9 | 1,753 | 4.0K | 1.7K |
| 10 | 5,007 | 13.2K | 4.6K |
| 11 | 14,274 | 42.2K | 23.9K |
| 12 | 40,954 | 122.5K | 64.5K |
| 13 | 117,548 | 357.9K | 172.4K |
| 14 | 338,485 | 1.0M | 477.0K |
| 15 | 975,721 | 3.0M | 1.3M |
| 16 | 2,817,871 | 8.6M | 3.5M |
| 17 | 8,146,510 | 24.9M | 10.0M |
| 18 | 23,581,381 | 72.3M | 28.5M |
| 19 | 68,322,672 | 212.9M | 83.3M |
| 20 | 198,138,512 | 633.0M | 252.6M |
...up to conjugation with no fixed points
The transformations with no fixed points up to conjugation (by elements of the symmetric group) of degrees 2 to 20 can be found below. The representatives with the lex-least image lists are given for those transformations of degree 2 to 10 but not for degrees 11 to 20.
The sequence of numbers of transformations with no fixed points up to conjugation is A001373 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 1 | 26.0B | 64.0B |
| 3 | 2 | 32.0B | 72.0B |
| 4 | 6 | 45.0B | 88.0B |
| 5 | 13 | 65.0B | 100.0B |
| 6 | 40 | 116.0B | 160.0B |
| 7 | 100 | 226.0B | 264.0B |
| 8 | 291 | 627.0B | 468.0B |
| 9 | 797 | 1.7K | 996.0B |
| 10 | 2,273 | 5.6K | 2.7K |
| 11 | 6,389 | 18.4K | 13.0K |
| 12 | 18,264 | 52.1K | 35.0K |
| 13 | 51,916 | 147.4K | 93.9K |
| 14 | 148,666 | 419.6K | 261.7K |
| 15 | 425,529 | 1.2M | 717.5K |
| 16 | 1,221,900 | 3.4M | 2.0M |
| 17 | 3,511,507 | 9.7M | 5.6M |
| 18 | 10,111,043 | 27.9M | 16.5M |
| 19 | 29,142,941 | 82.3M | 47.3M |
| 20 | 84,112,009 | 236.4M | 143.0M |
...up to conjugation with no fixed points and connected
The connected transformations with no fixed points up to conjugation (by elements of the symmetric group) of degrees 2 to 20 can be found below. The representatives with the lex-least image lists are given for those transformations of degree 2 to 10 but not for degrees 11 to 20.
The sequence of numbers of connected transformations with no fixed points up to conjugation is A002862 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 1 | 26.0B | 64.0B |
| 3 | 2 | 32.0B | 72.0B |
| 4 | 5 | 42.0B | 84.0B |
| 5 | 11 | 60.0B | 96.0B |
| 6 | 31 | 97.0B | 140.0B |
| 7 | 77 | 179.0B | 224.0B |
| 8 | 214 | 452.0B | 340.0B |
| 9 | 576 | 1.2K | 756.0B |
| 10 | 1,592 | 3.8K | 1.9K |
| 11 | 4,375 | 13.1K | 9.4K |
| 12 | 12,183 | 35.7K | 24.0K |
| 13 | 33,864 | 98.5K | 63.2K |
| 14 | 94,741 | 273.4K | 172.5K |
| 15 | 265,461 | 774.5K | 460.0K |
| 16 | 746,372 | 2.1M | 1.2M |
| 17 | 2,102,692 | 5.9M | 3.4M |
| 18 | 5,938,630 | 16.5M | 9.6M |
| 19 | 16,803,610 | 47.7M | 26.7M |
| 20 | 47,639,902 | 133.6M | 77.8M |
Pairs of transformations
...up to conjugation
Sets of transformations with two elements up to conjugation (by elements of the symmetric group) of degrees 2 to 7 can be found below, the representatives with the lex-least image lists are given.
The sequence of numbers of 2-element sets of transformations up to conjugation is A225772 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 4 | 77.0B | 84.0B |
| 3 | 67 | 218.0B | 228.0B |
| 4 | 1,455 | 3.3K | 1.2K |
| 5 | 41,829 | 99.0K | 15.8K |
| 6 | 1,540,566 | 3.6M | 531.6K |
| 7 | 68,342,769 | 164.2M | 19.5M |
...up to conjugation and strongly connected
Sets of transformations with two elements which are strongly connected and given up to conjugation (by elements of the symmetric group) can be found below, the representatives with the lex-least image lists are given.
The sequence of numbers of 1- and 2-element sets of transformations up to conjugation is A230326 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 3 | 38.0B | 80.0B |
| 3 | 28 | 99.0B | 148.0B |
| 4 | 459 | 1.0K | 772.0B |
| 5 | 10,700 | 25.1K | 6.6K |
| 6 | 329,793 | 779.6K | 145.7K |
| 7 | 12,310,960 | 29.8M | 3.8M |
...up to conjugation and synchronizing
Sets of transformations with two elements which are synchronizing (i.e. generate a semigroup which contains a constant transformation) and given up to conjugation (by elements of the symmetric group) can be found below, the representatives with the lex-least image lists are given.
The sequence of numbers of 1- and 2-element sets (up to conjugation) of transformations that generate a synchronizing semigroup is A230401 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 3 | 37.0B | 80.0B |
| 3 | 49 | 142.0B | 188.0B |
| 4 | 1,111 | 2.5K | 1.3K |
| 5 | 34,256 | 80.7K | 19.2K |
| 6 | 1,318,679 | 3.0M | 536.6K |
| 7 | 60,477,796 | 142.0M | 18.6M |
...up to conjugation, strongly connected, and synchronizing
Sets of transformations with two elements which are synchronizing (i.e. generate a semigroup which contains a constant transformation), strongly connected, and given up to conjugation (by elements of the symmetric group) can be found below, the representatives with the lex-least image lists are given.
The sequence of numbers of 2-element sets (up to conjugation) of transformations that generate a synchronizing strongly connected semigroup is A245686 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 2 | 34.0B | 80.0B |
| 3 | 21 | 84.0B | 128.0B |
| 4 | 395 | 903.0B | 700.0B |
| 5 | 10,180 | 23.9K | 6.5K |
| 6 | 322,095 | 760.9K | 148.1K |
| 7 | 12,194,323 | 29.5M | 3.9M |
Pairs of commuting transformations
The ordered pairs (f,g) of transformations which commute (i.e.
f(g(i))=g(f(i)) for all i) are given. These pairs were
found by Raad Al Kohli.
The sequence of numbers of order pairs sets of commuting transformations is A181162 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 10 | 58.0B | 96.0B |
| 3 | 141 | 363.0B | 380.0B |
| 4 | 2,824 | 7.1K | 4.2K |
| 5 | 71,565 | 176.2K | 79.6K |
| 6 | 2,244,096 | 5.4M | 1.9M |
Subsemigroups of the full transformation monoid
The non-empty subsemigroups of the full transformation monoids (up to conjugation) of degrees 2 to 4 can be found below. These were computed by Attila Egri-Nagy.
The sequence of numbers of subsemigroups of the full transformation monoid up to conjugation is A215651 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 8 | 46.0B | 92.0B |
| 3 | 282 | 806.0B | 832.0B |
| 4 | 132,069,775 | 1.9G |
Endomorphisms...
...of the full transformation monoid
The endomorphisms of the full transformation monoid on a finite set are described in:
Boris M. Schein and Beimnet Teclezghi, Endomorphisms of finite full transformation semigroups, Proc. Amer. Math. Soc. 126 (1998) 2579-2587.
The sequence of numbers of endomorphisms of the full transformation monoids is A226223 on the OEIS.
The endomorphism of the full transformation monoids on 2 to 6 points are given below as transformations on \(n^n\) points.
| degree | number | gz | xz |
|---|---|---|---|
| 2 | 7 | 68.0B | 84.0B |
| 3 | 40 | 186.0B | 208.0B |
| 4 | 345 | 1.4K | 1.1K |
| 5 | 3,226 | 19.8K | 9.6K |
| 6 | 38,503 | 288.6K | 155.3K |
Additionally, the endomorphisms of the full transformation monoid on 6 points are available in their right regular representation as transformations on \(38503\) points: gz (305K) or xz (193K).
...of connected graphs
Using the catalogues of connected graphs available at:
http://cs.anu.edu.au/~bdm/data/graphs.html
a C program written by Max Neunhoeffer which produces a relatively large list of endomorphisms containing a generating set for the endomorphism monoid, and the GAP package Semigroups we obtained small generating sets for the resulting monoids.
The generators appear in the order that the corresponding graphs appears in the files:
http://cs.anu.edu.au/~bdm/data/graph3c.g6
(where the appropriate value is substituted for \(3\)).
The sequence of numbers of connected graphs is A001349 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 3 | 2 | 53.0B | 80.0B |
| 4 | 6 | 86.0B | 116.0B |
| 5 | 21 | 215.0B | 264.0B |
| 6 | 112 | 1.2K | 1.1K |
| 7 | 853 | 13.4K | 11.6K |
| 8 | 11,117 | 302.4K | 239.2K |
| 9 | 261,080 | 21.6M | 17.2M |
...of Eulerian graphs
A graph is Eulerian if it admits an Eulerian path. A connected graph is Eulerian if and only if every vertex is of even degree.
Generators for the endomorphisms of the Eulerian graphs with 3 to 9 vertices can be found below. These were computed in the same way as the endomorphisms of connected graphs, described above.
The generators appear in the order that the corresponding graphs appears in the files:
http://cs.anu.edu.au/~bdm/data/eul3c.g6
(where the appropriate value is subsituted for \(3\)).
The sequence of numbers of connected Eulerian graphs is A003049 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 3 | 1 | 41.0B | 68.0B |
| 4 | 1 | 51.0B | 76.0B |
| 5 | 4 | 86.0B | 120.0B |
| 6 | 8 | 152.0B | 196.0B |
| 7 | 37 | 593.0B | 616.0B |
| 8 | 184 | 5.1K | 4.5K |
| 9 | 1,782 | 92.7K | 75.7K |
...of non-abelian groups
The table below contains generators for the endomorphism monoids of the non-abelian groups with at most 63 elements.
The groups were obtained from the Small groups library in GAP, the function Endomorphisms in the Sonata package for GAP was used to produce a list of all the endomorphisms, and the GAP package Semigroups was used to obtain a small generating set for the resulting monoid.
The sequence of numbers of non-abelian groups is A060689 on the OEIS.
| degree | number | gz | xz |
|---|---|---|---|
| 6 | 1 | 67.0B | 84.0B |
| 8 | 2 | 99.0B | 124.0B |
| 10 | 1 | 94.0B | 104.0B |
| 12 | 3 | 191.0B | 212.0B |
| 14 | 1 | 106.0B | 124.0B |
| 16 | 9 | 815.0B | 800.0B |
| 18 | 3 | 262.0B | 296.0B |
| 20 | 3 | 280.0B | 308.0B |
| 21 | 1 | 119.0B | 148.0B |
| 22 | 1 | 138.0B | 176.0B |
| 24 | 12 | 1.2K | 1.2K |
| 26 | 1 | 152.0B | 188.0B |
| 27 | 2 | 295.0B | 340.0B |
| 28 | 2 | 228.0B | 260.0B |
| 30 | 3 | 431.0B | 456.0B |
| 32 | 44 | 15.2K | 12.4K |
| 34 | 1 | 144.0B | 180.0B |
| 36 | 10 | 1.6K | 1.5K |
| 38 | 1 | 150.0B | 188.0B |
| 39 | 1 | 165.0B | 204.0B |
| 40 | 11 | 1.9K | 1.7K |
| 42 | 5 | 1.0K | 992.0B |
| 44 | 2 | 383.0B | 416.0B |
| 46 | 1 | 168.0B | 200.0B |
| 48 | 47 | 13.0K | 10.7K |
| 50 | 3 | 629.0B | 644.0B |
| 52 | 3 | 632.0B | 612.0B |
| 54 | 12 | 3.0K | 2.7K |
| 55 | 1 | 209.0B | 252.0B |
| 56 | 10 | 2.6K | 2.3K |
| 57 | 1 | 186.0B | 232.0B |
| 58 | 1 | 192.0B | 228.0B |
| 60 | 11 | 3.2K | 2.8K |
| 62 | 1 | 197.0B | 240.0B |
| 63 | 2 | 656.0B | 652.0B |