The Information Structuralist

A graph-theoretic derivation of the Gilbert-Varshamov bound

Posted in Coding Theory, Information Theory, Mathematics by mraginsky on September 23, 2013

Just a quick note for my reference, but it may be of interest to others.

Let {A_q(n,d)} denote the size of the largest code over a {q}-ary alphabet that has blocklength {n} and minimum distance {d}. The well-known Gilbert-Varshamov bound says that

\displaystyle  A_q(n,d+1) \ge \frac{q^n}{V_q(n,d)},


\displaystyle  V_q(n,d) = \sum^d_{i=0}{n \choose i}(q-1)^i

is the volume of a Hamming ball of radius {d} in {\{0,\ldots,q-1\}^n}. The usual way of arriving at the GV bound is through a greedy construction: pick an arbitrary codeword {x}, then keep adding codewords that are at Hamming distance of at least {d+1} from all codewords that have already been picked. When this procedure terminates, the complement of the union of the Hamming balls of radius {d} around each of the codewords should be empty — otherwise, you will have at least one more codeword at distance of at least {d+1} from the ones already picked, and this would mean that the procedure could not have terminated.

As it turns out, there is another way of deriving the GV bound using graph theory that I have learned from a nice paper by Van Vu and Lei Wu. They use this graph-theoretic interpretation to arrive at an asymptotic improvement of the GV bound. Their result, which I will not go into here, extends an earlier result by Tao Jiang and Alex Vardy for binary codes. As far as I can tell, the graph-theoretic ideas go back to the Jiang-Vardy paper as well.

In order to proceed, we need some definitions and a lemma. Let {G = (V,E)} be an undirected graph. A set {S \subseteq V} of vertices is called independent if no two vertices in {S} are connected by an edge. The independence number of {G}, denoted by {I(G)}, is the cardinality of the largest independent set. The following lemma is folklore in graph theory:

Lemma 1 Suppose that {G} is {D}-regular, i.e., every vertex has exactly {D} neighbors. Then

\displaystyle  	I(G) \ge \frac{|V|}{D+1}. \ \ \ \ \ (1)

Proof: Let {I} be a maximal independent set. Any vertex {v \in V\backslash I} is connected by an edge to at least one {v' \in I}, because otherwise {v} would have to be included in {I}, which would contradict maximality. Therefore, there are at least {|V \backslash I| = |V| - |I|} edges with one vertex in {I} and another vertex in {V \backslash I}. On the other hand, because {G} is {D}-regular, there can be at most {D|I|} such edges. This means that

\displaystyle  	D|I| \ge |V| - |I|.

Rearranging, we get (1). \Box

Now let us construct the following graph (what Jiang and Vardy call the Gilbert graph): associate a vertex to each word in {\{0,\ldots,q-1\}^n}, and connect two vertices by an edge if and only if the Hamming distance between the corresponding words is at most {d}. This graph has {q^n} vertices, and each vertex has degree {D = V_q(n,d)-1}. Moreover, there is a one-to-one correspondence between independent sets of vertices and {q}-ary codes of length {n} and minimum distance at least {d+1}, and the independence number of the Gilbert graph is equal to {A_q(n,d+1)}. The bound (1) is then precisely the GV bound.

Briefly, the Vu-Wu improvement of the GV bound exploits the deep fact that, when the neighborhood of any vertex in a {D}-regular graph is very sparse (in the sense that it has a lot fewer than {{D \choose 2}} edges), the lower bound (1) can be significantly tightened. Apparently, actually counting the number of edges in such a neighborhood of any vertex of the Gilbert graph (by regularity, we may as well look at the neighborhood of the all-zero word) is rather complicated; Vu and Wu instead look at a suitable asymptotic regime when {n} is large and {d = \alpha n} for some {\alpha \le 1-1/q} and replace exact combinatorial bounds by entropy bounds.

4 Responses

Subscribe to comments with RSS.

  1. Ankur Kulkarni said, on September 23, 2013 at 7:25 am

    Max, just and FYI. One can derive a similar lower bound for more general finite metric spaces (not just (q^n,Hamming)) using a generalization of the lemma you have. That generalization, called Turan’s theorem, gives I(G) \geq |V|/(\bar{d} +1}), where \bar{d} is the average degree of G.

    • mraginsky said, on September 23, 2013 at 3:09 pm

      Thanks, Ankur! My background is mostly in analysis, so I naturally think in terms of metric spaces, and the GV bound is a volume-counting argument. But the connections to graph theory (and in particular extremal graph theory) are fascinating.

      • Ankur Kulkarni said, on September 23, 2013 at 11:13 pm

        In fact, do look at the proof of Turan’s theorem in Alon and Spencer, The probablistic method. The proof is probablistic; and I am guessing it will resonate with you more than a set-packing proof.

  2. Ludo Tolhuizen said, on August 13, 2017 at 6:17 pm

    The relation between the Gilbert-Varshamov bound and Turan’s bound appeared in my paper from IEEE Transactions on Information Theory, Vol 43, 5, Sept 1997, pp. 1605-1606. Jiang and Vardy do cite my paper, but only state that it does not give a significant improvement, not that I mentioned the relation to graph theory. Later I heard from Gerard Cohen that he knew this too; I forgot if he said that it had appeared in French only.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: