# Space efficient representation of Regular graphs

Let $$G$$ be a $$k$$-regular graph (each vertex have a degreee $$k$$). It is trivial to store the graph in $$O(\log n)$$ space or words such that $$j$$th neighbour of any vertex can be found in $$O(\log n)$$ time. Assume that neighbours of each vertex are ordered.

Note that $$k=O(\log n)$$

Is there an representation of graph $$G$$ that takes $$o(nk)$$ space in words such that query can be solved in $$O(1)$$

• Just for my own curiosity, what is this trivial representation you talk about? – Tassle Oct 20 '19 at 13:19
• @Tassle either using adjacency list or array. – user110834 Oct 20 '19 at 15:09

No. Even ignoring the requirement to answer queries, you can't store such a graph in $$o(nk)$$ space, assuming each word is $$\Theta(\lg n)$$ bits long (i.e., each word has space to store the index of a single vertex).
In particular, there are $${n-1 \choose k}$$ ways to choose $$k$$ neighbors of a single vertex, so there are $${n-1 \choose k}^n$$ possible $$k$$-regular graphs. Now
$$\lg {n-1 \choose k}^n = n \lg {n-1 \choose k} = kn \lg(n/k) + \Theta(kn) = \Omega(kn \lg(n/k)).$$
Thus, information-theoretically, you need at least $$\Omega(kn \lg(n/k))$$ bits to store such a graph, or equivalently, at least $$\Omega(kn \lg(n/k)/\lg n)$$ words. Notice that for $$k=O(\log n)$$, we have $$\lg(n/k)/\lg n = \Theta(1)$$.
Therefore, we find that we need at least $$\Omega(kn)$$ words just to represent all possible $$k$$-regular graphs, so there is no hope for a data structure with space complexity $$o(kn)$$, even if you ignore the query time requirement.
• Your estimate for the number of $k$-regular graphs is a bit naive (you’re describing the bipartite case), but good bounds are known for values of $k$ which are not too large, and may imply your bound. – Yuval Filmus Nov 19 '19 at 19:35