MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 extended the question by a tiny bit

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and triangles? what about including more information, like number of tetrahedra, etc.? If not, why?

The solution to the unlabeled case with given number of nodes and edges, and to many other enumeration problems can be given in terms of Polya's theorem (by Harary, de Bruijn, Robinson, Read, Polya, etc.). Is it possible to give the resulting generating functions an interpretation in terms of order theory and use this to study their algebraic properties?

Are these generating function methods actually useful for computing these numbers when the graphs are 'large'? Thanks!

Update: Here is the list:

http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html

I haven't seen it in the OEIS, though.

Does it get any easy if we wanted to enumerate, instead, the set of graphs on given number of vertices and trangles -irrespective- of the number of edges?

2 added 134 characters in body

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and triangles? what about including more information, like number of tetrahedra, etc.? If not, why?

The solution to the unlabeled case with given number of nodes and edges, and to many other enumeration problems can be given in terms of Polya's theorem (by Harary, de Bruijn, Robinson, Read, Polya, etc.). Is it possible to give the resulting generating functions an interpretation in terms of order theory and use this to study their algebraic properties?

Are these generating function methods actually useful for computing these numbers when the graphs are 'large'? Thanks!

Update: Here is the list:

http://www.win.tue.nl/~aeb/graphs/cospectral/triangles.html

I haven't seen it in the OEIS, though.

1

# Number of graphs with a given number of nodes, edges and triangles

Hi. Does anyone know if it is possible to enumerate the set of labeled/unlabeled graphs (loopless, undirected, only one edge between pairs of nodes) having a given number of nodes, edges and triangles? what about including more information, like number of tetrahedra, etc.? If not, why?

The solution to the unlabeled case with given number of nodes and edges, and to many other enumeration problems can be given in terms of Polya's theorem (by Harary, de Bruijn, Robinson, Read, Polya, etc.). Is it possible to give the resulting generating functions an interpretation in terms of order theory and use this to study their algebraic properties?

Are these generating function methods actually useful for computing these numbers when the graphs are 'large'? Thanks!