# 60/102 Null Boundary Cellular Automata based expander graphs.

1 IntroductionExpander graphs were first defined by Bassalygo and Pinsker and their existence first proved by Pinsker in the early 1970s [10]. Also expander graphs have utility in computational settings such as in the theory of error correcting codes and the theory of pseudorandomness as well as a tool for proving results in number theory and computational complexity [6, 8, 11]. Expander graphs are useful in the design and analysis of communication networks. Mukhopadhyay et al. introduced a method to generate a family of expander graphs based on nongroup two predecessor single attractor Cellular Automata(CA). In this paper we propose a method to generate a family of expander graphs based on 60/102 Null Boundary CA(NBCA) which is a group CA. The merit of our method is that it use regular, modular and cascadable structure of 60/102 NBCA [1, 3, 4] to generate regular graphs of good expansion property with less storage. The spectral gap generated by our method is maximal. Moreover, the spectral gap is larger than that of Mukhopadhyay et al. [9].

2 Preliminaries

CA consist of a number of interconnected cells arranged spatially in a regular manner, where the state transition of each cell depends on the states of its neighbors. The CA structure investigated by Wolfram [12] can be viewed as a discrete lattice of sites (cells), where each cell can assume the value either 0 or 1. The next-state of a cell is assumed to depend on itself and on its two neighbors (3-neighborhood dependency). If the next-state function of a cell is expressed in the form of a truth table, then the decimal equivalent of the output is conventionally called the rule number for the cell.

Neighborhood state 111 110 101 100 010 001 000 Next state 0 0 1 1 1 0 0 Next state 0 1 1 0 1 1 0 Neighborhood state Next state rule 60 Next state rule 102

The top row gives all eight possible states of the three neighboring cells (the left neighbor of the ith cell, the ith cell itself, and its right neighbor) at the time of instant t. The second and third rows give the corresponding states of the ith cell at the time of instant t +1 for two illustrative CA rules.

Informally, expander graph is a graph G = (V, E) in which every subset S of vertices expands quickly, in the sense that it is connected to many vertices in the set [bar.S] of complementary vertices.

Definition 2.1 ([8]). Suppose G = (V, E) has n vertices. For a subset S of V define the edge boundary of S, [partial derivative]S, to be the set of edges connecting S to its complement [bar.S]. That is, [partial derivative]S consists of all those edges (v, w) such that v [member of] S and w [??] S. The expansion parameter for G is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [absolute value of X] denotes the size of a set X.

Example 2.2. Suppose G is the complete graph with n vertices, i.e., the graph in which every vertex is connected to every other vertex. Then for any vertex in S, each vertex in S is connected to all the vertices in [bar.S], and thus [absolute value of [partial derivative]S] = [absolute value of S] x [absolute value of [bar.S]] = [absolute value of S] (n - [absolute value of S]). It follows that the expansion parameter for G is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It is a marvellous fact that properties of the eigenvalue spectrum of the adjacency matrix A(G) can be used to understand properties of the graph G. This occurs so frequently that we refer to the spectrum of A(G) as the spectrum of the graph G. It is useful because the eigenvalue spectrum can be computed quickly, and certain properties, such as the largest and smallest eigenvalue, the determinant and trace, can be computed extremely quickly [8].

Let G = (V, E) be an undirected graph and A(G) be the adjacency matrix of the graph G. And let [[lambda].sub.i](A(G))(1 [less than or equal to] i [less than or equal to] n) be eigenvalues of A(G). Then A(G) is a real symmetric matrix and thus diagonalized. Without loss of generality we can assume that [[lambda].sub.1](A(G)) [greater than or equal to] [[lambda].sub.2](A(G)) [greater than or equal to] xxx [greater than or equal to] [[lambda].sub.n](A(G)).

Lemma 2.3. [1] Let C be a CA where state transition matrix T and C' be the complemented CA derived from C where state transition operator [bar.T]. And let [[bar.T].sup.p] denote p times application of the complemented CA operator [bar.T]. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where T is the characteristic matrix of the corresponding noncomplemented rule vector and F(x) is an n-dimensional vector (n=number of cells) responsible for inversion after XNORing. F (x) has '1' entries (i.e., nonzero entries) for CA cell positions where XNOR function is employed and f (x) is the current state assignment of the cells.

3 Properties of the eigenvalue spectrum

In this section, we give properties of the eigenvalue spectrum of the adjacency matrix A(G) of an undirected graph G. The following three theorems are well-known.

Theorem 3.1. Let G be an undirected d-regular graph whose adjacency matrix is A(G). Then [[lambda].sub.i](A(G)) = d.

Theorem 3.2. Let G be an undirected d-regular graph. Then G is connected if and only if [[lambda].sub.1](A(G)) > [[lambda].sub.2](A(G)).

Theorem 3.3. Let G be an undirected d-regular graph. Then G is bipartite if and only if [[lambda].sub.i](A(G)) = -[[lambda].sub.n+1-i](A(G)),i = 1,2, xxx ,n.

Now we define the gap for the d-regular graph G to be the difference [DELTA](G) [equivalent to] d - [[lambda].sub.2](A(G)).

Theorem 3.4. [2] Let G be a d-regular graph with spectrum [[lambda].sub.1](A(G)) [greater than or equal to] [[lambda].sub.2](A(G)) [greater than or equal to] xxx [greater than or equal to] [[lambda].sub.n](A(G)). Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Example 3.5. Let G be an undirected graph with the adjacency matrix A(G) as the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] -4. Moreover, [DELTA](G) = 4 - 2 [square root of (2)]. Thus [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Since [[lambda].sub.1](A(G)) [greater than or equal to] [[lambda].sub.2](A(G)) and [[lambda].sub.i](A(G)) = -[[lambda].sub.17-i](A(G))(i = 1, 2, xxx, 16), G is connected and bipartite.

4 60/102 NBCA based expander graphs

In this section we show a construction of a family of random d-regular graphs using 60/102 NBCA. Let C be the n-cell 60/102 NBCA whose state transition matrix T is as the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hereafter we write T by T = <60,102,102, xxx, 102>.

Clearly the characteristic (resp. minimal) polynomial c(x) (resp. m(x)) of T is c(x) = [(x + 1).sup.n] (resp. m(x) = [(x + 1).sup.n-i]). Since m(x) = [(x + 1).sup.n-i], we can obtain the following result. The proof of Theorem 4.1 is very similar to the proof of Theorem 3.4 in [3].

Theorem 4.1. Let C be the n-cell 60/102 NBCA with state transition matrix T =< 60,102,102, xxx, 102 >. Let C' be the complemented CA derived from C with complement vector [([a.sub.1], xxx ,[a.sub.n-i], 1).sup.t]([a.sub.i] [member of] {0,= 1, 2, xxx, n - 1 where [x.sup.t] is the transpose of the given vector x) and state transition operator [bar.T]. If ord(T) = [2.sup.a], then the following hold:

(a) all the lengths of cycles in C are the same.

(b) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark A. By Theorem 4.1, the state transition diagram of C' does not have any attractor.

Example 4.2. Let C be the 4-cell 60/102 NBCA whose state transition matrix is T =< 60,102,102,102 >. Then the structure and the state transition diagram of C are as in Figs. 1(a) and 1(b).

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

Let [F.sub.1] = [(0,0,0,1).sup.t]. Then by Lemma 2.3 [bar.T]0 =1, [bar.T]1 = 2, [bar.T]2 = 7, [bar.T]3 = 4, [bar.T]4 = 5, xxx, [bar.T]14 = 11 and [bar.T]15 = 8. Thus we obtain the state transition diagram [G.sub.1] of the state transition operator [bar.T] of the complemented CA [C'.sub.1] with complement vector [F.sub.1] = [(0,0,0,1).sup.t] of C. Also we see that ord([bar.T]) = ord(T) = 4 and all lengths of cycles in C are all the same by Theorem 4.1.

Fig. 1(b) shows the state transition diagram [G.sub.1] and [G.sub.2] of the complemented CA with [F.sub.1] = [(0,0,0,1).sup.t] and [F.sub.2] = [(1,1,1,1).sup.t] respectively whose two adjacency 8 x 8 matrices A([G.sub.1]) and A([G.sub.2]) respectively using Example 4.2 are as the following.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let G be the graph obtained by the union of the graphs [G.sub.1] and [G.sub.2]. Then A(G) is as the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The characteristic polynomial of A(G) is [x.sup.6](x - 4)(x + 4)[(x - 2).sup.4][(x + 2).sup.4]. Hence the eigenvalues of A(G) are [[lambda].sub.1] = 4, [[lambda].sub.2] = xxx = [[lambda].sub.5] = 2, [[lambda].sub.6] = xxx = [[lambda].sub.11] =0, [[lambda].sub.12] = xxx = [[lambda].sub.15] = -2, [[lambda].sub.16] = -4. Therefore by Theorem 3.2 and Theorem 3.3 G is connected and bipartite. Fig. 2 shows the graph G with the adjacency matrix A(G).

Theorem 4.3. Let C be the 60/102 NBCA whose state transition matrix is T. Let [C'.sub.1] (resp. [C'.sub.2]) be the complemented CA derived from C with the complement vector [F.sub.1] = [(0, *, xxx, *, 1).sup.t] (resp. [F.sub.2] = [(1, *, xxx, *, 1).sup.t]). Also let [[bar.T].sub.1]X = TX [direct sum] [F.sub.1] and [[bar.T].sub.2]X = TX [direct sum] [F.sub.2]. Let [G.sub.1] (resp. [G.sub.2]) be the graph obtained from [C'.sub.1] (resp. [C'.sub.2]). And let G be the union of two graphs [G.sub.1] and [G.sub.2] whose adjacency matrix is A([G.sub.1]) and A([G.sub.2]) respectively. Then G is a bipartite 4-regular graph.

Table 1 shows the eigenvalue spectrum of A(G) which is the union of [G.sub.1] and [G.sub.2]. In Table 1 let [F.sub.1] = [(0,1,1,1).sup.t] and [F.sub.2] = [(1,1,0,1).sup.t]. Then the eigenvalue spectrum of A(G) is [[lambda].sub.1] = 4, [[lambda].sub.2] = xxx = [[lambda].sub.5] = 2, [[lambda].sub.6] = xxx = [[lambda].sub.11] = 0, [[lambda].sub.12] = xxx = [[lambda].sub.15] = -2, [[lambda].sub.16] = -4. Therefore in this case the graph G is a bipartite 4-regular graph.

Table 2 shows the result of an experimentation performed with the 60/102 NBCA based regular graph. It measures the value of the two largest eigenvalues for random 60/102 NBCA based graphs for degree 4, 8,12 and 16. Our results show that the spectral gap and hence the expansion increases proportionately with the number of union operations (t). Table 3 shows that the spectral gap by the our method is larger than the spectral gap by Mukhopadhyay's method [9].

Theorem 4.4. Let C be the n-cell 60/102 NBCA. Also let x = [([x.sub.1],[x.sub.2], xxx,[x.sub.n]).sup.*] be a state of the state transition diagram of the state transition matrix T of C. Then the immediate predecessor y = [([y.sub.1], [y.sub.2], xxx, [y.sub.n]).sup.t] of x satisfies the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark B. It is easy to see that the inverse matrix [T.sup.-1] of T is of the following form.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

So the required time to get the immediate predecessors is O(n). For the given n-cell 60/102 NBCA, the construction of d-regular graphs which have the maximum spectral gaps depend on the relationship between [F.sub.1] and [F.sub.2]. For example, in Table 1 let F = [(0,0,0,1).sup.t] and [F.sub.2] = [(1,1,1,1).sup.t]. Then the spectral gap is 2 which is the maximum value in the 4-regular graph.

Now let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and let U = ([F.sub.11] x [F.sub.21]) [union] ([F.sub.12] x [F.sub.22]).

Choose the complement vectors [F.sub.1], [F.sub.2] such that ([F.sub.1], [F.sub.2]) [member of] U. Let [G.sub.1] (resp. [G.sub.2]) be the graph with [F.sub.1] (resp. [F.sub.2]). Then we can construct an expander graph where spectral gap is maximal.

The following algorithm shows computing the four neighbors of a vertex in G which is the union of [G.sub.1] and [G.sub.2] .

Algorithm (Computing neighbors of a vertex in G).

Input: Complement vectors ([F.sub.1], [F.sub.2]) [member of] K and a state x [member of] G.

Output: The four neighbors ([S.sub.1], [S.sub.2], [P.sub.1], [P.sub.2]) of x.

Step 1: Find the next state [S.sub.1] (resp. [S.sub.2]) of x using the operator [T.sub.1] (resp. [T.sub.2]).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

/* Find the immediate predecessor [P.sub.1] (resp. [P.sub.2]) by using Theorem 4.4 in Step 2 and Step 3 */

Step 2: Compute W := x [direct sum] [F.sub.1] and V := x [direct sum] [F.sub.2].

Step 3: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

In general the description of an expander d-regular graph grows exponentially with the number of vertices as the increase of the size of 60/102 NBCA. However as we require to store only two complement vectors [F.sub.1] and [F.sub.2], this problem is solved by the above algorithm.

5 Conclusion

In this paper, we proposed a method to generate expander graphs with good expansion properties based on group 60/102 NBCA. The expansion properties by our method is better than the expansion properties proposed by Mukhopadhyay et al.

References

[1] P. Pal Chaudhuri, D. Roy Chowdhury, S. Nandi, and S. Chattopadhyay. Additive cellular automata theory and its application i, ieee computer society press, california. IEEE Computer Society Press, California, 2000.

[2] J. Cheeger. A lower bound for the smallest eigenvalue of the laplacian. in problems in analysis(papers dedicated to solomon bochner, 1969, 195-199). Princeton Univ. Press, 1970.

[3] S.J. Cho, U.S. Choi, H.D. Kim, and Y.H. Hwang. Analysis of complemented ca derived from linear hybrid group ca, computers and mathematics with applications. Computers and Mathematics with Applications, 53:54-63, 2007.

[4] S.J. Cho, U.S. Choi, H.D. Kim, Y.H. Hwang, J.G. Kim, and S.H. Heo. New synthesis of one dimensional 90/150 linear hybrid group cellular automata. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26:1720-1724, 2007.

[5] W. Diffie and M. Hellman. New direction in cryptography. IEEE Transaction on Information Theory, pages 644-654, 1976.

[6] D.Peleg and E.Upfal. Constructing disjoint paths on expander graphs. Combinatorica, pages 289-313, 1989.

[7] O. Goldreich. Candidate one-way functions based on expander graphs. Cryptology ePrint Archieve, Report 200/063, pages 1-9, 2000.

[8] S. Hoory, N. Lindal, and A. Wigderson. Expander graphs and their applications. Bull. AMS, 2006.

[9] D. Mukhopadhyay and D.R. Chowdhury. Generation of expander graphs using cellular automata and its applications to cryptography. LNCS, 4173:636-645, 2006.

[10] M.S. Pinsker. On the complexity of a concentrator. In 7th International Telegraffic Conference, pages 1-4, 1973.

[11] M. Sipser and D. Spielman. Expander codes. IEEE Transactions on Information Theory, 42:1710-1722, 1996.

[12] S. Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55:601-644, 1983.

Sung-Jin Cho (1), ([dagger]) Un-Sook Choi (2) Han-Doo Kim (3) Yoon-Hee Hwang (1) Jin-Gyoung Kim (1)

(1) Department of Applied Mathematics, Pukyong National University, Busan 608-737, Korea

(2) Department of Media Engineering, Tongmyong University, Busan 626-847, Korea

(3) School of Computer Aided Science, Institute of Basic Science, Inje University, KimHae 621-749, Korea

([dagger]) This work was supported by the Pukyong University Research Fund in 2009(PK-2009-26).

Tab. 1: The eigenvalue spectrum of A(G). The eight vectors on the first row(resp. column) are the complement vectors [F.sub.1](resp. [F.sub.2]) 0000 0010 0100 0110 0001 1000 -4(2) -4(1) -4(2) -4(1) 1100 0(10) -2(4) 0(10) -2(4) -4(1) 4(4) 0(4) 4(4) 0(4) -2.8284(2) 2(4) 2(4) -2(2) 4(3) 4(3) 0(6) 1010 -4(1) -4(2) -4(1) -4(2) 2(2) 1110 -2(4) 0(10) -2(4) 0(10) 2.8284(2) 0(4) 4(4) 0(4) 4(4) 4(1) 2(4) 2(4) 4(3) 4(3) 1001 -4(2) 1101 0(12) -2.8284(2) -2.8284(2) -2.8284(2) -2.8284(2) 4(2) -2(2) -2(2) -2(2) -2(2) 0(6) 0(6) 0(6) 0(6) 1011 2(2) 2(2) 2(2) 2(2) -4(1) 1111 2.8284(2) 2.8284(2) 2.8284(2) 2.8284(2) -2(4) 4(2) 4(2) 4(2) 4(2) 0(6) 2(4) 4(1) 0011 0101 0111 1000 1100 -4(1) -4(1) -4(1) -2.8284(2) -2.8284(2) -2.8284(2) -2(2) -2(2) -2(2) 0(6) 0(6) 0(6) 1010 2(2) 2(2) 2(2) 1110 2.8284(2) 2.8284(2) 2.8284(2) 4(1) 4(1) 4(1) 1001 -4(1) -4(2) -4(1) 1101 -2(4) 0(12) -2(4) 0(6) 4(2) 0(6) 2(4) 2(4) 4(1) 4(1) 1011 -4(2) -4(1) -4(2) 1111 0(12) -2(4) 0(12) 4(2) 0(6) 4(2) 2(4) 4(1) Tab. 2: Spectrum of the 4-cell 60/102 NBCA based regular graph No. of Complement Degree First Second Union (t) vector Eigenvalue Eigenvalue 1 1,15 4 4 2 3 1,3,9,15 8 8 4 5 1,3,5,9,11,15 12 12 2 7 1,3,5,7,9,11,13,15 16 16 0 No. of Spectral g/t Union (t) Gap (g) 1 2 2 3 4 1.33 5 10 2 7 16 2.2857 Tab. 3: Comparison of Mukhopadhyay's spectral gaps with our spectral gaps No. of Union (t) g/t(Mukhopadhyay's method) g/t(Our method) 1 0.76 2 3 1.03 1.33 5 1.14 2 7 1.54 2.2857

Printer friendly Cite/link Email Feedback | |

Author: | Cho, Sung-Jin; Choi, Un-Sook; Kim, Han-Doo; Hwang, Yoon-Hee; Kim, Jin-Gyoung |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jan 1, 2010 |

Words: | 3312 |

Previous Article: | Faster methods for identifying nontrivial energy conservation functions for cellular automata. |

Next Article: | Probabilistic initial value problem for cellular automaton rule 172. |

Topics: |