Redfield's Theorems and Multilinear Algebra

White, Dennis E.

Canadian journal of mathematics, Tome 27 (1975) no. 3, pp. 704-714

Résumé

1. Introduction. The remarkable 1927 paper by J. H. Redfield [13] which anticipated many recent combinatorial results in Polya counting theory and, in fact, predated Polya's theorem by ten years has been discussed at length by Harary and Palmer [8], Foulkes [5; 6], Sheehan [15; 16] and Read [12], not to mention de Bruijn [3] and others. We shall, in this paper, demonstrate how multilinear techniques may be used in this context. The Redfield superposition theorem and decomposition theorem turn out to be statements about a group acting on finite function spaces, and may thus be dealt with in multilinear terms. We shall prove Redfield's results and an extension due to Foulkes [5].

Détail

DOI : 10.4153/CJM-1975-078-x

Bibliographie

[1] 1. Boerner, H., Representations of groups (John Wiley and Sons, Inc., New York, 1963). Google Scholar

[2] 2. Burnside, W., Theory of groups of finite order, Second edition (Cambridge University Press, Cambridge, 1911, Dover Publications, 1955). Google Scholar

[3] 3. deBruijn, N. G., Enumerative combinatorial problems concerning structures, Nieuw Arch. Wisk. 3 (1963), 142–161. Google Scholar

[4] 4. deBruijn, N. G., Polya's theory of counting, in Beckenbach, E. F., Applied combinatorial mathematics (John Wiley and Sons, Inc., New York, 1964), 144–184. Google Scholar

[5] 5. Foulkes, H. O., On Redfield's group reduction functions, Can. J. Math. 15 (1963), 272–284. Google Scholar

[6] 6. Foulkes, H. O., On Redfield's range-correspondences, Can. J. Math. 18 (1966), 1060–1071. Google Scholar

[7] 7. Hall, M. Jr., The theory of groups (The Macmillan Co., New York, 1959). Google Scholar

[8] 8. Harary, F. and Palmer, E., The enumeration methods of Red field, Amer. J. Math. 89 (1967), 373–384. Google Scholar

[9] 9. Littlewood, D. E., The theory of group characters, Second edition (Oxford University Press, Oxford, 1950). Google Scholar

[10] 10. Perlman, D., Computational methods for pattern enumeration and isomorph rejection, Ph.D. Thesis, University of California, San Diego, 1973. Google Scholar

[11] 11. Polya, G., Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254. Google Scholar

[12] 12. Read, R. C., The use of S-functions in combinatorial analysis, Can. J. Math. 20 (1968), 808–841. Google Scholar

[13] 13. Redfield, J. H., The theory of group-reduced distributions, Amer. J. Math. 49 (1927), 433–455. Google Scholar

[14] 14. De, G. Robinson, B., Representation theory of the symmetric group (Edinburgh University Press, Edinburgh, 1961). Google Scholar

[15] 15. Sheehan, J., The number of graphs with a given automorphism group, Can. J. Math. 20 (1968), 1068–1076. Google Scholar

[16] 16. Sheehan, J., On Polyas theorem, Can. J. Math. 19 (1967), 792–799. Google Scholar

[17] 17. White, D. E., Classifying patterns by automorphism group: an operator theoretic approach, Discrete Math, (to appear). Google Scholar

[18] 18. White, D. E., Construction of vector lists and isomorph rejection (to appear). Google Scholar

[19] 19. White, D. E., Linear and multilinear aspects of isomorph rejection, Linear and Multilinear Algebra (to appear). Google Scholar

[20] 20. White, D. E., Multilinear enumerative techniques, Linear and Multilinear Algebra #(1975), 341–352. Google Scholar

[21] 21. Williamson, S. G., Isomorph rejection and a theorem of deBruijn, Siam J. Computing 2 (1973), 44–59. Google Scholar