Question:
If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like?
Are there any patterns that emerge as $n$ becomes large? Are there some concentration results saying that the probability tends to cluster around certain isomorphism classes? Has this sort of thing been studied, if so what are some good references?
Motivation:
In statistical mechanics, a large number of indistinguishable "microstates" of a system may correspond to a single "macrostate", and the entropy of that macrostate is defined as the log of it's number of microstates.
The motivation is to define an analogous entropy for graphs, where the microstates are the graphs and the macrostates are the isomorphism classes. The entropy $H$ is then defined as,
$$H(\text{isomorphism class}) = \log \left(\frac{\text{# of graphs in the class}}{\text{total number of graphs}}\right)$$
Example:
Since I don't know the right terms to search for or words to use, the best I can do is try to illustrate by example. Take all 4-vertex graphs (64 of them) and consider enumerating all graphs in the various isomorphism classes; there is
- 1 graph with no edges, the entropy of this class would be $H = \log(1/64)$:
- 6 isomorphic graphs with one edge, the entropy of this class would be $H = \log(6/64)$:
- 12 isomorphic graphs with two edges that are connected, $H = \log(12/64)$:
- 3 isomorphic graphs with two edges that are disconnected, $H = \log(3/64)$:
and so on.
For completeness, the rest of the isomorphism classes are:
- 4 isomorphic graphs with three edges that are cyclic with one disconnected vertex:
- 12 isomorphic graphs with three edges that form a "chain":
- 4 isomorphic graphs with three edges that "fan out" from one vertex:
- 3 isomorphic graphs with four edges that form a big loop:
- 12 isomorphic graphs with four edges that have a small loop with one edge offshoot:
- 6 isomorphic graphs with five edges:
- 1 complete graph:
These counts form a distribution on the "meta-graph" where nodes are isomorphism classes, and edges are present whenever one isomorphism class can be transformed into another by adding or removing a single edge:
This problem seems like it should be well studied, but I don't know enough about the field to know the terms to search for or literature to look through. Searching for "graph ismorphism" and the like is such a broad topic. It's easy to find information about counting how many isomorphism classes there are, but I can't find much about counting the number of graphs within the isomorphism classes.
Edit:
I computed the isomorphism counts for all 5-vertex graphs, and made the following plot. Can't see much of a pattern though.
Best Answer
Since almost all graphs are asymmetric, almost all isomorphism classes of graphs on $n$ vertices have size $n!$.