MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). What is known about this problem? And if it is a hard problem, what are the difficulties?

The only reference I have been able to find is Asymptotic Enumeration of 2-Covers and Line Graphs by Cameron, Prellberg and Stark, which indirectly deals with the 2-regular case.

Any help or reference would be much appreciated.

share|cite|improve this question
You can consider the problem of counting hypergraphs on n vertices with specified degrees of the vertices as counting partitions of a multiset in which each block is a set. Some references for this problem can be found in my paper Symmetric Functions and P-Recursiveness, J. Combin. Theory Ser. A 53 (1990), 257–285, – Ira Gessel Dec 10 '13 at 20:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.