1
$\begingroup$

According to answers here https://math.stackexchange.com/questions/1524598/a-general-incidence-problem// an unigraph comes from unigraphic degree sequences if it can be uniquely determined by its degree sequences.

Adjacency matrix or incidence matrix of a graph provides every computable information about a graph.

Apart from degree sequences what additional information would one need to provide to capture any graph uniquely? That is degree sequence plus some additional information should give as much information on a graph as possible. What is this additional information?

Adjacency matrix needs about $2 n^2\log n$ bits of information (to specify a row and column you need to spend $\log n + \log n$ bits and we have $n^2$ combinations of rows and columns). If we choose to represent a graph by fixing an order on vertices, you still need $n^2$ bits (same as adjacency matrix).

Degree sequences need about $n\log n$ bits of information.

So we are missing a factor of $2n$ or $\frac n{\log n}$ depending on how we look.

It is clear degree sequences are insufficient. Information theoretically we need to provide incidence relations. Is there a way to specify this information implicitly so that a multiplicative factor of $n$ is taken care of while we do not add additionally the degree information?


That is can we separate the degree information from this additional multiplicative piece? Is there a meaning to this multiplicative factor? Thinking of indices and conditional entropies only gives you additive meaning. This means you get only quadratic factors back.

$\endgroup$
  • 2
    $\begingroup$ The number of graphs is $2^{\binom n2}$ and the number of isomorphism classes asymptotically $2^{\binom n2}/n!$, so that tells you how many bits are definitely needed. If we all agreed on a ordering of all graphs, we could specify any graph in minimum space by giving its index number. This shows the problem is not well defined. $\endgroup$ – Brendan McKay Nov 12 '15 at 0:06
  • $\begingroup$ @BrendanMcKay Why do you say it is not well defined? I am just seeking a way to describe conditional information on a graph conditioned on its degree information? this is well formed notion. $\endgroup$ – user76479 Nov 12 '15 at 0:08
  • 1
    $\begingroup$ A related question is whether in polynomial time enough invariants of the graph can be computed so that the isomorphism class is identified uniquely. That is basically the graph isomorphism problem , which is highly unsolved. $\endgroup$ – Brendan McKay Nov 12 '15 at 0:17
  • 1
    $\begingroup$ But many sequences of integers from $0..n$ are not degree sequences. The minimum number of bits is $log_2$ of the number of different degree sequences. (I think that is known...) $\endgroup$ – Brendan McKay Nov 12 '15 at 0:19
  • 1
    $\begingroup$ "The $i$-th integer sequence in lexicographic order that is a degree sequence for some graph" is how to specify a degree sequence using the least number of bits in the worst case. But I think I have a sort of answer to your question; I'll post it as an answer shortly. $\endgroup$ – Brendan McKay Nov 12 '15 at 0:27
6
$\begingroup$

I'll address the question like this: if you are given the degree sequence of a graph, what is the most number of additional bits that you might need to provide to uniquely identify the graph?

The answer to this depends on how many graphs can have the same degree sequence, and also on whether labelled graphs or isomorphism classes are being considered.

As far as I'm aware, it is not known which degree sequence has the most graphs in either case. For labelled graphs, when you know the labelled degree sequence and you don't count permutations of it as being the same, there is some evidence that for large enough $n$ sequences close to $\frac{n-1}2,\frac{n-1}2,\ldots,\frac{n-1}2$ will win (I'm not allowing loops). The number of labelled graphs with any given degree sequence like that is asymptotically $$\Theta(1) \frac{2^{n^2/2}}{\pi^{n/2}n^{n/2}},$$ see this paper. So in this case you can get by with $$\frac{n^2}2 - \frac{n\log_2 (\pi n)}2 + O(1)$$ bits and this is a lower bound on how many bits might be needed in the worst case. If computational complexity is ignored, the information can be provided in that many bits by giving an index number ("the $i$-th graph with the given degree sequence").

$\endgroup$
  • 1
    $\begingroup$ Thank you for the answer. I see what you are stating. You are right conditional entropy is additive. So you get a quadratic additive factor back (I have noticed that). However is there a way to give meaning to the multiplicative factor? I think that answer would be most helpful in graph related questions. $\endgroup$ – user76479 Nov 12 '15 at 3:07

Your Answer

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