<p>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.</p>

CC BY-SA 3.0
2016-08-16T03:35:41.030Z
2016-08-16T03:35:41.030Z
Palash Dey
<p>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.  </p>

CC BY-SA 3.0
2016-08-15T15:40:37.313Z
The answer is no. I have already see it in this post: http://cstheory.stackexchange.com/questions/41/succinct-circuit-representation-of-graphs
Frank Vega
CC BY-SA 3.0
2016-08-15T15:40:41.123Z
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)$.
Emil Jeřábek
<cc.complexity-theory>
Is it possible to find always a succinct representation of an arbitrary graph?
Frank Vega
# Is it possible to find always a succinct representation of an arbitrary graph?

(Asked by: username_0 on 2016-08-15)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_0**: The answer is no. I have already see it in this post: http://cstheory.stackexchange.com/questions/41/succinct-circuit-representation-of-graphs  
> **username_1**: 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)$.  

---

## 1 answers

### Answer by username_2 on 2016-08-16. Score: 0 | Accepted answer

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.


---

