Hypergraphs, characteristic polynomials and permutation characters

Abstract

An (n m) hypergraph is a coupleH=(N E), where the vertex set N is {1,…n} and the edge set E is an m-element multiset of nonempty subsets of N. In this paper, we count nonisomorphic hypergraphs where isomorphism of hypergraphs is the natural extension of that of graphs. A main result is an explicit formula for the cycle index of the permutation representation of any permutation group P with object set N acting on the k-element subsets of N. By making a simple substitution in these cycle indices for P the symmetric group S_N and k=1,…,n, we obtain generating functions which enumerate various types of hypergraphs. Using the technique developed, we extend Snapper's results on characteristic polynomials of permutation representations and group characters from the case where the group has odd order to the general case.