Let $G = (V,E)$ be a directed graph where every vertex is represented by an $n$ bit string. The edges are represented by two polynomial-sized circuits $S$ and $P$. There is an edge from $u$ to $v$ if and only if $S(u) = v$ and $P(v) = u$. I am trying to prove:

  • $G$ just contains paths, cycles, or isolated vertices.
  • Let $A_{G}$ be the adjacency matrix of $G$. Consider $H = \frac{1}{2} A_{G}$. Then, $||H||_{2} = 1$.
  • $\begingroup$ The out-degree and in-degree of each vertex are at most 1. Does that help? $\endgroup$ – Yuval Filmus Oct 13 at 9:01
  • $\begingroup$ Why do we need to divide by $1/2$ for the second case? Isn't $||A_{G}||_{2} = 1$ already? $\endgroup$ – BlackHat18 Oct 13 at 9:28
  • 1
    $\begingroup$ I am guessing that this relates to the fact that there could be vertices of degree 2. $\endgroup$ – Yuval Filmus Oct 13 at 9:39
  • $\begingroup$ As in, a vertex which has out-degree 1 and also a self-loop? $\endgroup$ – BlackHat18 Oct 13 at 9:48
  • $\begingroup$ No, as in all vertices in a (directed) cycle. $\endgroup$ – Yuval Filmus Oct 13 at 10:07

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.