om a search for a lower bound on $d(n,l_2)$. But why limit the discussion to Euclidean space? What can be said of spherical embeddings into $l_1$ or $l_{\infty}$? The former may be particularly interesting, as it will give a non-trivial lower bound on $d(n,l_1)$.\
We have seen that $\frac n 2$-regular graphs with bounded second eigenvalue are $o(n^2)$-close to complete bipartite. However, the only example we know of such graphs are constructed by taking a complete bipartite graph, and changing a constant number of edges for each vertex. These graphs are $O(n)$-close to being complete bipartite. Are there examples of such families which are further from complete bipartite graphs, or can a stonger notion of closeness be proved?

Acknowledgments
===============

We would like to thank Alex Samorodnitsky for showing us how to prove Lemma \[alex\] and Noga Alon for sending us Lemma \[d-lemma\].

[^1]: Institute of Computer Science, Hebrew University Jerusalem 91904 Israel . This research is supported by the Israeli Ministry of Science and the Israel Science Foundation.


---
abstract: 'We consider graph states of arbitrary number of particles undergoing generic decoherence. We present methods to obtain lower and upper bounds for the system’s entanglement in terms of that of considerably smaller subsystems. For an important class of noisy channels, namely the Pauli maps, these bounds coincide and thus provide the exact analytical expression for the entanglement evolution. All the results apply also to (mixed) graph-diagonal states, and hold true for any convex entanglement monotone. Since any state can be locally depolarized to some graph-diagonal state, our method provides a lower bound for the entanglement decay of any arbitrary state. Finally, this formalism also allows for the direct identification of the robustness under size scaling of graph states in the presence of decoherence, merely by inspection of their connectivities.'
author:
- Daniel Cavalcanti
- Rafael Chaves
- Leandro Aolita
- Luiz Davidovich
- Anton