Timeline for Quantitatively characterizing the failure of the converse of Dirac's theorem
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 11, 2020 at 21:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Sep 11, 2020 at 20:54 | answer | added | Ben Barber | timeline score: 1 | |
| Sep 11, 2020 at 19:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 21, 2018 at 2:10 | history | edited | 1729 | CC BY-SA 4.0 |
added 656 characters in body
|
| Nov 21, 2018 at 1:21 | history | edited | 1729 | CC BY-SA 4.0 |
added 527 characters in body
|
| Nov 20, 2018 at 17:06 | comment | added | Nate Eldredge | So, maybe you want to skip the probability language, and just say "What fraction of unlabeled Hamiltonian graphs on $n$ vertices satisfy the Dirac condition?" It's probably hopeless to get an exact closed-form answer, but you could hope for asymptotics. | |
| Nov 20, 2018 at 16:37 | history | edited | 1729 | CC BY-SA 4.0 |
deleted 733 characters in body
|
| Nov 20, 2018 at 16:32 | comment | added | 1729 | @GerhardPaseman Ahh. Your right something must be up with my maple code. For example $C_3$ clearly satisfies Dirac's condition. Will update my answer accordingly. | |
| Nov 20, 2018 at 15:55 | comment | added | Gerhard Paseman | Why are p3 through p6 zero? There is at least one graph satisfying Dirac's condition. Gerhard "Probably It Is The Complement?" Paseman, 2018.11.20. | |
| Nov 20, 2018 at 15:40 | comment | added | 1729 | @NateEldredge Reading over the entire question I agree now that it is unclear what probability I was interested in. I'm pretty sure I meant the conditional probability you mentioned (question updated now). I was considering the case of G being drawn uniformly from the set of non isomorphic hamiltonian graphs. However, just reading over your comments it is clear that I much more work to do in probability and graph theory before I can really investigate something like this! | |
| Nov 20, 2018 at 15:39 | history | edited | 1729 | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Nov 20, 2018 at 15:02 | comment | added | Nate Eldredge | Also, I suppose your question is about the probability that every vertex of $G$ is of degree at least $n/2$. In which case you ought to write $P(G \in H_n \text{ and } \operatorname{deg}(v) \ge \frac{n}{2} \forall v \in G)\}$. But maybe you'd also be interested in the conditional probability $P( \operatorname{deg}(v) \ge \frac{n}{2} \forall v \in G \mid G \in H_n)$, which seems more along the lines of your question. | |
| Nov 20, 2018 at 14:59 | comment | added | Nate Eldredge | I don't quite understand the question. I guess you want $G$ to be a random graph on $n$ vertices, but from what probability model? Uniformly over all $2^{\binom{n}{2}}$ labeled graphs? Uniformly over unlabeled graphs (probably really hard)? Uniformly over (labeled or unlabeled) Hamiltonian graphs? Erdős–Rényi? Something else? (More formally, you have to specify a probability measure on the set of all graphs on $n$ vertices.) | |
| Nov 20, 2018 at 14:38 | history | edited | 1729 | CC BY-SA 4.0 |
added 659 characters in body
|
| Nov 19, 2018 at 23:57 | history | edited | 1729 |
edited tags
|
|
| Nov 19, 2018 at 21:37 | history | edited | 1729 | CC BY-SA 4.0 |
added 1 character in body
|
| Nov 19, 2018 at 20:55 | review | First posts | |||
| Nov 19, 2018 at 21:28 | |||||
| Nov 19, 2018 at 20:52 | history | asked | 1729 | CC BY-SA 4.0 |