How many different graphs of order $n$ are there?
2
$begingroup$
I'm interested in all four combinations: directed and undirected, cyclic and acyclic.
I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).
My best guess on a DAG is close to Ω(n!).
[Edit: "multigraphs", obviously, aren't part of the question.]
[Edit2: Looks like for DCGs, it is about 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
$endgroup$
add a comment |
2
$begingroup$
I'm interested in all four combinations: directed and undirected, cyclic and acyclic.
I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).
My best guess on a DAG is close to Ω(n!).
[Edit: "multigraphs", obviously, aren't part of the question.]
[Edit2: Looks like for DCGs, it is about 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
$endgroup$
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17
add a comment |
2
2
2
$begingroup$
I'm interested in all four combinations: directed and undirected, cyclic and acyclic.
I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).
My best guess on a DAG is close to Ω(n!).
[Edit: "multigraphs", obviously, aren't part of the question.]
[Edit2: Looks like for DCGs, it is about 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
$endgroup$
I'm interested in all four combinations: directed and undirected, cyclic and acyclic.
I'm having trouble calculating how big the complexity gets as you add more nodes to a graph. Clearly, the number of possible graphs goes up with adding directability, and wildly (adding Ω(2n) complexity, roughly).
My best guess on a DAG is close to Ω(n!).
[Edit: "multigraphs", obviously, aren't part of the question.]
[Edit2: Looks like for DCGs, it is about 24*n. For DAGs, it's about 23*n.]
[Note: I tagged this under "descriptive complexity" because it's not really a simulation. Let me know if this is wrong.]
graph-theory combinatorial-geometry descriptive-complexity
graph-theory combinatorial-geometry descriptive-complexity
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
edited Jan 9 at 21:12
theDoctor
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
asked Nov 19 '18 at 17:37
theDoctortheDoctor
215213
215213
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17
add a comment |
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17
add a comment |
1 Answer
1
active
oldest
votes
6
$begingroup$
In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.
Graphs
- Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $S~$II.5 gives that this sequence is asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
- Acyclic graphs on $n$ nodes (forests) is A005195:
$$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$. - Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$.
Directed graphs
- Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
- Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
$endgroup$
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005230%2fhow-many-different-graphs-of-order-n-are-there%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
6
$begingroup$
In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.
Graphs
- Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $S~$II.5 gives that this sequence is asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
- Acyclic graphs on $n$ nodes (forests) is A005195:
$$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$. - Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$.
Directed graphs
- Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
- Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
$endgroup$
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
add a comment |
6
$begingroup$
In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.
Graphs
- Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $S~$II.5 gives that this sequence is asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
- Acyclic graphs on $n$ nodes (forests) is A005195:
$$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$. - Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$.
Directed graphs
- Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
- Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
$endgroup$
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
add a comment |
6
6
6
$begingroup$
In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.
Graphs
- Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $S~$II.5 gives that this sequence is asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
- Acyclic graphs on $n$ nodes (forests) is A005195:
$$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$. - Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$.
Directed graphs
- Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
- Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
$endgroup$
In general these counts do not have nice closed formulas, but some satisfy nice recurrence relations.
Graphs
- Graphs on $n$ nodes is OEIS A000088: $$1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ldots .$$ Flajolet & Sedgwick's Analytic Combinatorics, $S~$II.5 gives that this sequence is asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$. (They cite Harary & Palmer's text Graphical Enumeration for this fact, but I haven't checked it myself. Probably that reference gives some of the below data, too.)
- Acyclic graphs on $n$ nodes (forests) is A005195:
$$1, 1, 2, 3, 6, 10, 20, 37, 76, 153, ldots .$$ This is asymptotic to $c n^{-5/2} d^n$ for some $c > 0$ and $d > 1$. - Cyclic graphs on $n$ nodes is A286743: $$0, 0, 1, 5, 24, 136, 1007, 12270, 274515, 12004839, ldots .$$ By definition this is just [A000088] - [A005195]. The latter has much smaller growth than the former, so this also asymptotic to $2^{frac{1}{2} n (n - 1)}/n!$.
Directed graphs
- Directed graphs on $n$ nodes is OEIS A000273: $$1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, ldots .$$ This is asymptotic to $2^{n (n - 1)}/n!$
- Directed acyclic graphs on $n$ nodes is OEIS A003087: $$1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, ldots .$$ OEIS doesn't give asymptotics for this sequence, but we can deduce from asymptotics for the case of labeled directed acyclic graphs that this sequence is asymptotic to some function in between $A p^{-n} 2^{frac{1}{2} n (n - 1)}$ and $A p^{-n} 2^{frac{1}{2} n (n - 1)} n!$ for some $A > 0$ and $p > 1$. In any case before this is much slower growth than the count for directed graphs, so graphs on $n$ nodes that have at least one cycle is also asymptotic to $2^{n (n - 1)} / n!$.
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
edited Nov 19 '18 at 22:21
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
answered Nov 19 '18 at 19:31
TravisTravis
61.1k767147
61.1k767147
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
add a comment |
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
1
1
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
A compact Maple routine for OEIS A000088 may be found at the following MSE link (scroll to end of post, is not limited to question from title of link).
$endgroup$
– Marko Riedel
Nov 19 '18 at 20:01
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
That is amazing. Thanks for the answer! I will evaluate further.
$endgroup$
– theDoctor
Nov 19 '18 at 21:27
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
You're welcome. I've added a reference to A286743.
$endgroup$
– Travis
Nov 19 '18 at 22:24
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
@Travis: My analysis says a DAG should be asymptotic to 2<sup>3n</sup> and a DCG to 2<sup>4n</sup>. I tested my asymptotic on DCG and it was more accurate, but there's not much data.
$endgroup$
– theDoctor
Nov 28 '18 at 21:30
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
$begingroup$
I haven't redone the calculation myself, but the cited rate for D.A.G. comes from the linked OEIS entry, which cites: M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports 17 (1955), 14-22. A hand-annotated pdf copy can be found at oeis.org/A000088/a000088.pdf In that article the relevant sequence is denoted $textrm{ref}_n$.
$endgroup$
– Travis
Nov 29 '18 at 13:32
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3005230%2fhow-many-different-graphs-of-order-n-are-there%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Labeled or unlabeled? (For instance, are there $frac12 n!$ path graphs on $n$ vertices, or only $1$?)
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:06
$begingroup$
In my understanding of "labeled" graphs, there would be an infinite number, so it's inapplicable.
$endgroup$
– theDoctor
Nov 19 '18 at 19:07
$begingroup$
Labeled graphs in the sense that we name the vertices $v_1, v_2, dots, v_n$ (or if you prefer just $1, 2, dots, n$) and go from there. This is the standard thing to do when, for example, we count labeled trees. Another way to phrase my question: do you want to count isomorphic graphs multiple times or not?
$endgroup$
– Misha Lavrov
Nov 19 '18 at 19:10
$begingroup$
@MishaLavrov: No isomorphic graphs are not counted multiple times. Labeling a graph was not considered proper graph theory in my education, any more than putting the mileage on the edges between cities.
$endgroup$
– theDoctor
Nov 19 '18 at 19:17