-2
$\begingroup$

When I said a succinct representation of a graph of n nodes, I meant a Boolean circuit C of 2*b input gates (where b = |n| and |n| is the binary string length of n), such that for every b-bits integers i and j, then C accepts the input i and j if and only if (i, j) is an edge of the graph and the size of C is O(b^{k}), that is polylogarithmic in relation to n.

$\endgroup$

closed as off-topic by Emil Jeřábek, David Eppstein, Sasho Nikolov, Mohammad Al-Turkistany, Robin Kothari Aug 16 '16 at 13:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, David Eppstein, Sasho Nikolov, Mohammad Al-Turkistany, Robin Kothari
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ The answer is no. I have already see it in this post: cstheory.stackexchange.com/questions/41/… $\endgroup$ – Frank Vega Aug 15 '16 at 15:40
  • 3
    $\begingroup$ No. An obvious information-theoretic argument tells you that random graphs whp cannot be described using less than $\binom n2$ bits, hence they need exponential circuit size $\Omega(n^2/\log n)=\Omega(2^{2b}/b)$. $\endgroup$ – Emil Jeřábek Aug 15 '16 at 15:40
0
$\begingroup$

With n vertices, there are $O(2^{n \choose 2})$ possible labelled graphs (based on which edges are present). So you need ${n\choose 2}$ bits to store.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.