= 27d567bc2d48d9f40e9ccc20ea370b15)
IlyaShpitser comments on Confound it! Correlation is (usually) not causation! But why not? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (34)
Naively, I would expect it to be closer to 600^600 (the number of possible directed graphs with 600 nodes).
And in fact, it is some complicated thing that seems to scale much more like n^n than like 2^n: http://en.wikipedia.org/wiki/Directed_acyclic_graph#Combinatorial_enumeration
If we allow cycles, then there are three possibilities for an edge between a pair of vertices in a directed graph: no edge, or an arrow in either direction. Since a graph of n vertices has n choose 2 pairs, the total number of DAGs of n vertices has an upper bound of 3^(n choose 2). This is much smaller than n^n.
edit: the last sentence is wrong.
Gwern, thanks for writing more, I will have more to say later.
It is much larger.
= ^{n-1})^n)
, and ^{n-1})
is much larger than n.
3^(10 choose 2) is about 10^21.
Since the nodes of these graphs are all distinguishable, there is no need to factor out by graph isomorphism, so 3^(n choose 2) is the exact number.
The precise asymptotic is%202%5E{\binom{n}{2}}%20\omega%5E{-n})
, as shown on page 4 of this article. Here lambda and omega are constants between 1 and 2.
That's the number of all directed graphs, some of which certainly have cycles.
So it is. 3^(n choose 2) >> n^n stands though.
A lower bound for the number of DAGs can be found by observing that if we drop the directedness of the edges, there are 2^(n choose 2) undirected graphs on a set of n distinguishable vertices, and each of these corresponds to at least 1 DAG. Therefore there are at least that many DAGs, and 2^(n choose 2) is also much larger than n.
Yup you are right, re: what is larger.