Timeline for Approximating distance on a finite graph with Hamming distance
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 22 at 3:41 | history | bounty ended | David Gao | ||
| S Mar 22 at 3:41 | history | notice removed | David Gao | ||
| Mar 22 at 3:41 | vote | accept | David Gao | ||
| S Mar 15 at 19:40 | history | bounty started | David Gao | ||
| S Mar 15 at 19:40 | history | notice added | David Gao | Draw attention | |
| Mar 13 at 18:48 | comment | added | David Gao | @DominicvanderZypen Thank you for the interesting reference! | |
| Mar 13 at 14:27 | answer | added | Daniel Weber | timeline score: 7 | |
| Mar 13 at 7:50 | comment | added | Dominic van der Zypen | A little bit related: arxiv.org/abs/1901.03409 | |
| Mar 13 at 6:38 | comment | added | David Gao | @CommandMaster Oh, well, thank you for the effort in any case. If you manage to fix the gap and obtain a solution for either that specific case or the general case, please write an answer and I’ll happily accept it. Thanks again! | |
| Mar 13 at 6:23 | comment | added | Daniel Weber | Sorry, apparently what I thought about doesn't work, nevermind | |
| Mar 13 at 6:05 | comment | added | David Gao | @CommandMaster Ah, that would be enough for what I need. Do you mind writing a full answer on the approach you mentioned for this specific case? I’m willing to accept that as the answer. Thank you so much! | |
| Mar 13 at 6:02 | comment | added | Daniel Weber | By bounded-degree graphs I meant that $N$ can also depend on the maximum degree, not only $\epsilon$. In particular, this implies what you said. | |
| Mar 13 at 6:01 | comment | added | David Gao | @CommandMaster By “bounded-degree graphs”, do you mean there exists some $d = d(\epsilon)$ such that if the maximum degree of the graph $G$ is bounded by $d$, then the result holds? If $d(\epsilon) \to \infty$ as $\epsilon \to 0$, that would actually be enough for my purpose. | |
| Mar 13 at 5:58 | comment | added | David Gao | @CommandMaster Not really, no. Graph theory is not my main research area, so I have basically no clue whatsoever about this. I just stumbled upon this question from a completely unrelated question in my field, so I felt it might be better to seek help from people with expertise in graph theory and such. | |
| Mar 13 at 5:33 | comment | added | Daniel Weber | A possible approach would be to randomly remove edges with some probability, and then give each vertex a value based on the component it's in, and do that enough times. What I've described above foils it, but perhaps there's still something which can be done. It does work for bounded-degree graphs. | |
| Mar 13 at 5:07 | comment | added | Daniel Weber | Currently I'm stuck on the case of two nodes, and many many disjoint paths of length $N$ between them. Do you have a solution for this case? | |
| Mar 13 at 4:01 | history | asked | David Gao | CC BY-SA 4.0 |