Complete graphs are good expanders. Deleting few edges from a complete graph leaves a good expander. What's the proportion of edges that one needs to remove to make the graph a bad expander? Or, is there any probabilistic result?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ This is not an answer but rather a comment, but since I can not add comments, I had to add it as an answer. These slides could be useful, they discuss sparsification of graphs including the compete graph. You can also find video talks of Daniel Spielman discussing the problem. $\endgroup$– AbbasCommented Apr 16, 2015 at 14:37
-
$\begingroup$ have a look at ams.org/journals/bull/2012-49-01/S0273-0979-2011-01359-3 $\endgroup$– Dima PasechnikCommented Apr 16, 2015 at 19:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Depends on your definition of 'expansion', but the answer will always be to remove all edges across some cut, and you should make this as small as possible. So for example if you insist on all sets of size $t$ having expansion (and not for any smaller sets), then you need to remove $t(n-t)$ edges to destroy expansion. It doesn't make much difference if you say you only want to destroy `good' expansion as opposed to any expansion at all.
Probabilistically, things are very different. The random graph is a good expander for very small $p$, again what $p$ depends on your definition of expansion; if you insist on all sets of sizes between $\varepsilon n$ and $(1-\varepsilon)n$ having good expansion (for some $\varepsilon>0$ fixed) then $p$ can be on the order $\log n/n$.
