Timeline for Asymptotic formula for the number of connected graphs
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 3, 2019 at 16:51 | history | edited | Aidan Rocke | CC BY-SA 4.0 |
fixed Flajolet reference as per Slava Rychkov's recommendation
|
| Jul 1, 2019 at 20:03 | comment | added | Brendan McKay | Incidentally, the proof is wrong. The probability of a particular $k$-set being disconnected from the rest is $2^{-k(N-k)}$. Multiply by $\binom Nk$ for the number of $k$-sets, then sum over $k=1\ldots N-1$ (or $k=1\ldots N/2$ if you like). You will see that the term for $k=1$ is easily the largest. | |
| Jul 1, 2019 at 18:13 | vote | accept | Aidan Rocke | ||
| Jul 1, 2019 at 16:03 | history | edited | Aidan Rocke | CC BY-SA 4.0 |
fixed last inequality
|
| Jul 1, 2019 at 15:41 | comment | added | Gerhard Paseman | Combinatorics and overcounting is another way. There are N choose k ways to divide the vertex set into a disconnected set of size k and one of size N-k, and the number of labeled graphs on the pair that are disconnected has 2 to a significantly smaller exponent than N choose 2, giving that disconnected graphs are fewer in number by a factor of about (2^(N-1))/N. Gerhard "Simple Arguments Really Do Count" Paseman, 2019.07.01. | |
| Jul 1, 2019 at 15:10 | history | edited | Aidan Rocke | CC BY-SA 4.0 |
added addendum
|
| Jul 1, 2019 at 2:11 | comment | added | Aidan Rocke | @lambda That makes sense now. As suggested by Olivier, an approach via random graphs might yield a much simpler demonstration that almost all simple graphs are connected without requiring the full asymptotic. I'm thinking about such a proof right now. | |
| Jun 30, 2019 at 15:58 | comment | added | lambda | Perhaps what isn't immediately obvious (at least it took me a little bit when I learned it) is that the Erdős–Rényi random graph model with edge probability 1/2 gives the uniform distribution on labelled graphs and so a statement about "almost all labelled graphs" in this sense is directly equivalent to one about random graphs in the usual sense. | |
| Jun 30, 2019 at 10:20 | comment | added | Olivier | I'm not a graph theorist either, but the statement seemed intuitive to me (it is quite hard for a large random graph not too be connected). Anyway, the article The $k$‐Connectedness of Unlabelled Graph by Walsh and Wright contains a much stronger statement. | |
| Jun 30, 2019 at 4:32 | history | edited | Aidan Rocke | CC BY-SA 4.0 |
correction of 'n' vertices to 'N' vertices
|
| Jun 30, 2019 at 4:31 | comment | added | Aidan Rocke | @Olivier I'm curious about your statement as I have a growing interest in graph theory but I'm not a graph theorist. Might you know of an elementary demonstration? | |
| Jun 30, 2019 at 2:01 | comment | added | Olivier | "So for large $N$ almost all labeled graphs are connected" Surely that conclusion can be obtained in a much simpler way than with the full asymptotic. | |
| Jun 30, 2019 at 0:37 | history | answered | Aidan Rocke | CC BY-SA 4.0 |