Timeline for Expected doubling constant of a random Erdős–Rényi graph
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 8, 2022 at 13:07 | history | bounty ended | ABIM | ||
| S Nov 8, 2022 at 13:07 | history | notice removed | ABIM | ||
| Nov 8, 2022 at 13:07 | vote | accept | ABIM | ||
| Nov 8, 2022 at 13:07 | vote | accept | ABIM | ||
| Nov 8, 2022 at 13:07 | |||||
| Nov 6, 2022 at 17:38 | answer | added | hdur | timeline score: 2 | |
| Nov 6, 2022 at 0:44 | comment | added | ABIM | I imagined it fixed but both are okay, if one is easier. | |
| Nov 5, 2022 at 22:46 | comment | added | François G. Dorais | Are you keeping $p$ fixed or is it a function of $n$? | |
| S Nov 5, 2022 at 20:40 | history | bounty started | ABIM | ||
| S Nov 5, 2022 at 20:40 | history | notice added | ABIM | Authoritative reference needed | |
| Nov 5, 2022 at 13:35 | history | edited | ABIM | CC BY-SA 4.0 |
added 2 characters in body
|
| Nov 4, 2022 at 15:25 | comment | added | ABIM | @usul It looks to me that this remark is indeed correct. | |
| Nov 4, 2022 at 11:52 | comment | added | usul | @VladimirZolotov when the graph is locally a tree, which it sometimes is, the answer should be much larger, right? A binary tree on $2^n$ nodes looks like it has doubling constant around $2^{n/2}$ to me: B(root, n) covers all nodes, but any ball of radius n/2 can only cover $2^{n/2}$ leaves, so $2^{n/2 - 1}$ balls are needed. [New to this, let me know if I misunderstand.] | |
| Nov 4, 2022 at 9:39 | comment | added | Vladimir Zolotov | (Expected) maximal degree is a lower bound. At the first glance if feels like this should be pretty close to the correct answer. Do you have something outperforming it? | |
| Nov 3, 2022 at 20:56 | history | edited | ABIM | CC BY-SA 4.0 |
deleted 9 characters in body
|
| Nov 3, 2022 at 20:44 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Nov 3, 2022 at 20:39 | history | asked | ABIM | CC BY-SA 4.0 |