2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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, people.brandeis.edu/~gessel/homepage/papers/dfin.pdf $\endgroup$
    – Ira Gessel
    Dec 10, 2013 at 20:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.