Timeline for Number of Geodesic Paths Passing Through a Vertex in an Expander Graph
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 13, 2011 at 3:21 | comment | added | ght | Can you give some indication at least of why do you think this is the case? | |
| Dec 12, 2011 at 23:41 | comment | added | kassabov | Sorry I've messed my estimate, this construction gives significantly more geodesic paths going through the extra edge -- I think the number is $T(G_n) > n^{4/3}$ but I might be wrong.. | |
| Dec 12, 2011 at 14:49 | comment | added | ght | Actually, it is not difficult to see that for any graph $G$ (expander or not) $T(G)\geq |G|-1$ and therefore your lower bound is too weak. This also shows that your proposed upper bound cannot work. | |
| Dec 12, 2011 at 8:46 | history | answered | kassabov | CC BY-SA 3.0 |