Timeline for More expanders?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Mar 25, 2013 at 10:07 | vote | accept | Seva | ||
| Mar 24, 2013 at 2:37 | answer | added | Noam D. Elkies | timeline score: 7 | |
| Mar 22, 2013 at 22:22 | comment | added | Noam D. Elkies | On further thought, Freddie Manners is right: neither (1) nor (2) can be an expander, and (3) should be. Details later if nobody posts the proof first. | |
| Mar 22, 2013 at 20:26 | comment | added | Noam D. Elkies | True, but nor is it of bounded degree. Still, you're basically right: joining two expanders of the same size with a bridge doesn't yield an expander. Still this should be close... | |
| Mar 22, 2013 at 20:16 | comment | added | Seva | The union of, say, three cliques with a bridge between any pair of them has a very small diameter, but is not an expander? | |
| Mar 22, 2013 at 19:08 | comment | added | Noam D. Elkies | Any field element is $e P(g)$ for some polynomial $P$ of degree $<n$. Thus it can be reached from $0$ in at most $2n$ steps. But I'm not sure whether this implies that the graph is an expander (the reverse direction is known). | |
| Mar 22, 2013 at 18:46 | comment | added | Seva | @Noam: sorry, do not get it. First, any (non-zero) field element is actually just a power of $g$. Second, I do not see why the diameter being logarithmic implies that the graph is an expander. (To my understanding, it does not - am I missing something? Could you expand? :-) ) | |
| Mar 22, 2013 at 18:12 | comment | added | Noam D. Elkies | The second graph has bounded degree and diameter logarithmic in the number of vertices (because any field element is $e$ times a polynomial in $g$); isn't that enough to make it an expander? | |
| Mar 22, 2013 at 17:51 | comment | added | Seva | @Freddie Manners: concerning the first graph I mentioned - you are absolutely right, pretty stupid of me not to notice this myself. Concerning the second graph - I still don't see any obvious reason for it not to be an expander. | |
| Mar 22, 2013 at 12:15 | comment | added | Freddie Manners | My guess is that (1) and (2) are doomed not to expand because they are "too abelian", or "too nilpotent". So for (1), a set like $\{\pm g^{n} : 0 \le n \le N \}$ for $N$ large (but small compared to $p$) is likely to contradict expansion. Something similar should work in (2), considering a set of bounded length words on both your generators. I think this is closely related to this MO question. (3) has a very different flavour. It might be related to expansion in $SL_2$. | |
| Mar 22, 2013 at 10:21 | history | edited | Nick Gill |
corrected spelling of tag
|
|
| Mar 22, 2013 at 8:40 | history | asked | Seva | CC BY-SA 3.0 |