Data

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.

degreenumbergzxz
2334.0B72.0B
3748.0B88.0B
41976.0B120.0B
547133.0B180.0B
6130292.0B316.0B
7343727.0B596.0B
89512.0K1.1K
92,6155.8K2.4K
107,31818.8K6.5K
1120,49160.2K43.0K
1257,903171.4K119.3K
13163,898491.5K330.6K
14466,1991.4M919.4K
151,328,9934.0M2.6M
163,799,62411.4M7.6M
1710,884,04932.7M21.7M
1831,241,17094.2M62.1M
1989,814,958275.9M177.8M
20258,604,642809.7M512.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.

degreenumbergzxz
2292.0B164.0B
3439.0B80.0B
4953.0B92.0B
52077.0B116.0B
651134.0B172.0B
7125268.0B268.0B
8329673.0B420.0B
98621.7K1.0K
102,3115.6K2.5K
116,21719.4K13.0K
1216,94952.6K33.0K
1346,350143.9K85.3K
14127,714395.8K227.3K
15353,2721.1M596.7K
16981,7533.0M1.5M
172,737,5398.2M4.2M
187,659,78922.9M11.8M
1921,492,28665.0M32.3M
2060,466,130183.0M93.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.

degreenumbergzxz
2184.0B156.0B
3335.0B76.0B
41060.0B100.0B
52799.0B148.0B
679207.0B244.0B
7218497.0B456.0B
86221.4K860.0B
91,7534.0K1.7K
105,00713.2K4.6K
1114,27442.2K23.9K
1240,954122.5K64.5K
13117,548357.9K172.4K
14338,4851.0M477.0K
15975,7213.0M1.3M
162,817,8718.6M3.5M
178,146,51024.9M10.0M
1823,581,38172.3M28.5M
1968,322,672212.9M83.3M
20198,138,512633.0M252.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.

degreenumbergzxz
2126.0B64.0B
3232.0B72.0B
4645.0B88.0B
51365.0B100.0B
640116.0B160.0B
7100226.0B264.0B
8291627.0B468.0B
97971.7K996.0B
102,2735.6K2.7K
116,38918.4K13.0K
1218,26452.1K35.0K
1351,916147.4K93.9K
14148,666419.6K261.7K
15425,5291.2M717.5K
161,221,9003.4M2.0M
173,511,5079.7M5.6M
1810,111,04327.9M16.5M
1929,142,94182.3M47.3M
2084,112,009236.4M143.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.

degreenumbergzxz
2126.0B64.0B
3232.0B72.0B
4542.0B84.0B
51160.0B96.0B
63197.0B140.0B
777179.0B224.0B
8214452.0B340.0B
95761.2K756.0B
101,5923.8K1.9K
114,37513.1K9.4K
1212,18335.7K24.0K
1333,86498.5K63.2K
1494,741273.4K172.5K
15265,461774.5K460.0K
16746,3722.1M1.2M
172,102,6925.9M3.4M
185,938,63016.5M9.6M
1916,803,61047.7M26.7M
2047,639,902133.6M77.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.

degreenumbergzxz
2477.0B84.0B
367218.0B228.0B
41,4553.3K1.2K
541,82999.0K15.8K
61,540,5663.6M531.6K
768,342,769164.2M19.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.

degreenumbergzxz
2338.0B80.0B
32899.0B148.0B
44591.0K772.0B
510,70025.1K6.6K
6329,793779.6K145.7K
712,310,96029.8M3.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.

degreenumbergzxz
2337.0B80.0B
349142.0B188.0B
41,1112.5K1.3K
534,25680.7K19.2K
61,318,6793.0M536.6K
760,477,796142.0M18.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.

degreenumbergzxz
2234.0B80.0B
32184.0B128.0B
4395903.0B700.0B
510,18023.9K6.5K
6322,095760.9K148.1K
712,194,32329.5M3.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.

degreenumbergzxz
21058.0B96.0B
3141363.0B380.0B
42,8247.1K4.2K
571,565176.2K79.6K
62,244,0965.4M1.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.

degreenumbergzxz
2846.0B92.0B
3282806.0B832.0B
4132,069,7751.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.

degreenumbergzxz
2768.0B84.0B
340186.0B208.0B
43451.4K1.1K
53,22619.8K9.6K
638,503288.6K155.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.

degreenumbergzxz
3253.0B80.0B
4686.0B116.0B
521215.0B264.0B
61121.2K1.1K
785313.4K11.6K
811,117302.4K239.2K
9261,08021.6M17.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.

degreenumbergzxz
3141.0B68.0B
4151.0B76.0B
5486.0B120.0B
68152.0B196.0B
737593.0B616.0B
81845.1K4.5K
91,78292.7K75.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.

degreenumbergzxz
6167.0B84.0B
8299.0B124.0B
10194.0B104.0B
123191.0B212.0B
141106.0B124.0B
169815.0B800.0B
183262.0B296.0B
203280.0B308.0B
211119.0B148.0B
221138.0B176.0B
24121.2K1.2K
261152.0B188.0B
272295.0B340.0B
282228.0B260.0B
303431.0B456.0B
324415.2K12.4K
341144.0B180.0B
36101.6K1.5K
381150.0B188.0B
391165.0B204.0B
40111.9K1.7K
4251.0K992.0B
442383.0B416.0B
461168.0B200.0B
484713.0K10.7K
503629.0B644.0B
523632.0B612.0B
54123.0K2.7K
551209.0B252.0B
56102.6K2.3K
571186.0B232.0B
581192.0B228.0B
60113.2K2.8K
621197.0B240.0B
632656.0B652.0B