Graphs, designs and difference sets

Abstract

Combinatorics is the branch of Mathematics, which deals with the problems of selecting and arranging objects in accordance with certain specified rules. In particular, a combinatorial design is a way of choosing, from a given finite set, a collection of subsets with given properties. The study of design was begun by Euler in 1782. While the first major result on the theory of block designs was due to Fisher in 1926.

A (v,k,λ.) difference set is a k- element subset D of a group G of order v for which the multiset {d₁d₂⁻¹ : d₁,d₂ ε D, d₁ d₂} contains each non-identity element of G exactly λ. times.

When an automorphism group acts regularly on the points and blocks of a block design, there is a simple way to represent the design. As a result of this action, this design correspond to difference sets and the correspondence between designs and difference sets is well known.

We have observed that complete graphs can be used to construct difference sets. The equivalence of complete graphs, designs and difference sets is established by the following theorem.

Theorem 1: Let G be a finite cyclic group of order n² +n + 1; n ≥ 2, and let D be a subset of G with n +1 elements. Then the following statements are equivalent:

(i). There is a complete graph of order n² +n +1 (ii). There is a ( n² +n +1, n +1, 1) - square design such that G acts regularly as an automorphism group. (iii). D is a difference set with parameters (n² + n +1, n +1, 1) This result is illustrated by means of several examples. Moreover, we have proved on Theorem 2 that this result can be generalized to regular graphs.

Theorem2: Let G be a finite cyclic group of order v and let D be a subset of G with k elements. Then the following statements are equivalent: (i) There is a λ (v -1)-regular graph of order v, (ii) There is a (v,k,λ.) -square design such that G acts regularly as an automorphism group. (iii) D is a difference set with parameters (v,k,λ.).

These combinatorial designs and difference sets are all used for construction of codes and sequences in digital communication systems.