Suppose you are given a directed graph $G=(V,E)$.

Define $P(G)=(V',E')$ to have as a vertex set the power set of $V$ minus $\emptyset$. A pair $v=\{v_1,\dots,v_i\},w=\{w_1,\dots,w_k\}\in V'$ is connected by a directed edge $v\to w$ edge if there is a subset of $E$ such that for every pair $(v_\ell,w_{\ell'})\in v\times w$, there is a directed edge in $E$ from $v_\ell\to w_{\ell'}$.

Is there a name for $P(G)$? Or perhaps a closely related construction?

  • $\begingroup$ Have you ever found out? $\endgroup$ – theV0ID Aug 18 '20 at 0:30
  • $\begingroup$ No, I never did. $\endgroup$ – batconjurer Oct 20 '20 at 21:16

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.