Suppose $G$ is a random graph on $n$ vertices where each edge appears with probability half. Suppose someone looks at the resulting graph and chooses an arbitrary subset $W$ of vertices of size $k>\sqrt{n}$. How do the eigenvalues of the induced subgraph $G[W]$ behave? In other words can we say that for every $W$ of size $k$, the eigenvalues of $G[W]$ will be close or related to that of a random graph from $G(k,1/2)$?

  • $\begingroup$ Are the edges in $G$ independently chosen? If so, I don't know how $G[W]$ is different from $G(k,1/2)$. $\endgroup$ – Willard Zhan Mar 13 '18 at 18:44
  • 1
    $\begingroup$ @WillardZhan, yes. It's different because $W$ might be a function of $G$, e.g., $W=f(G)$. i.e., imagine an adversary who sees the chosen graph $G$, then tries to choose a vertex set $W$ so that $G[W]$ has unusual eigenvalues. Can the adversary do that? It's not clear. I can certainly arrange that $G[W]$ doesn't follow a $G(k,1/2)$ distribution: e.g., find any triangle in $G$, and let $W$ be those three vertices; then $G[W]$ is always a triangle (probability 1), but $G(k,1/2)$ would be a triangle with probability just $1/8$. $\endgroup$ – D.W. Mar 13 '18 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.